class Linear
{
 int size;
 int num;
 int data[];

 //申請空間，如果用戶輸入的空間大小小于等于0，則默認使用空間100
 public Linear(int n)
 {
  if(n <= 0)
   size = 100;

  else
   size = n;

  data = new int[size];
  num = 0;
 }
 //遍歷所有的數據，并輸出
 public void Visit()
 {
  if(num == 0)
  {
   System.out.println("Visit:The array is empty!");
   return;
  }

  for(int i = 0; i < num; i++)
   System.out.print(data[i]+"\t");

  System.out.println();
 }
 //插入一個數據
 public void Insert(int pos,int x)
 {
  if(pos < 0 || pos > num)
  {
   System.out.println("Insert:The position is error!");
   return;
  }
  
  if(num == size)
  {
   System.out.println("Insert:The array is full!");
   return;
  }

  for(int i = num - 1; i >= pos; i--)
  {
   data[i+1] = data[i];
  }

  data[pos] = x;

  num ++;
 }
 //刪除一個數據
 public void Delete(int pos)
 {
  if(pos < 0 || pos > (num - 1))
  {
   System.out.println("Delete:The position is error!");
   return;
  }

  if(num == 0)
  {
   System.out.println("Delete:The array is empty!");
   return;
  }

  for(int i = pos; i < (num - 1); i++)
   data[i] = data[i+1];

  num -- ;
 }
 //選擇排序法,從小到大排列
 public void SelectSort()
 {
  int k = 0,p = 0,t = 0;

  for(int i = 0; i < num -1; i++)
  {
   t = data[i];
   k = i;
   p = i;

   for(int j = i + 1; j < num; j++)
    if(t > data[j])
    {
     t = data[j];
     p = j;
    }

   if(k != p)
   {
    int temp = data[k];
    data[k] = data[p];
    data[p] = temp;
   }
  }
 }
 //插入排序法，從小到大
 public void InserSort()
 {
  int i = 0,j = 0;

  for(i = 0; i < num; i++)
  {
   int t = data[i]; 
  
   for(j = i - 1; j >= 0; j --)
   {
    if(t < data[j])
     data[j+1] = data[j];
    else
     break;
   }

   data[j+1] = t;
  }
 }
 //冒泡排序
 public void BubbleSort()
 {
  int t = 0;

  for(int i = 0; i < num -1; i++)
   for(int j = i+1; j < num; j++)
    if(data[i] > data[j])
    {
     t = data[i];
     data[i] = data[j];
     data[j] = t;
    }
 }
 //快速排序，因為要使用遞歸，因此必須定義一個額外的快排方法
 private void qsort(int low,int high)
 {
  int i = 0, j = 0 ,t = 0;
  
  if(low < high)
  {
   i = low;
   j = high;
   t = data[low];

   while(i < j)
   {
    while((i < j) && (data[j] > t)) j--;

    if(i < j)
     data[i++] = data[j];

    while((i < j) && (data[i] <= t)) i++;

    if( i < j)
     data[j--] = data[i];
   }

   data[i] = t;

   qsort(low,j - 1);
   qsort(j + 1,high);
  }
 }

 public void QuickSort()
 {
  qsort(0,num - 1);
 }
}

class Program
{
 public static void main(String arg[])
 {
  //使用Linear線形結構
  Linear line = new Linear(5);

  //初始化若干數據,即插入5條數據

  line.Insert(0,3);
  line.Insert(1,7);
  line.Insert(2,2);
  line.Insert(3,5);
  line.Insert(4,3);

  //line.SelectSort();
  //line.InserSort();
  //line.BubbleSort();
  line.QuickSort();

  line.Visit();

  
 }
}