Category: Programming and Algorithm

今天来说说排序把,

1. Selection Sort(选择排序)

void SelectionSort(int*a, int n)
{
        for(int i=0; i<n; i++)
       {           temp = i;
              for(int j=i+1; j<n; j++)
                   if(a[j]<a[temp])  temp = j;
               swap(&a[temp], &a[i]);
         }
}

SelectionSort的想法很直接, 如果让你做排序, 一个没学过算法的人可能会想, 先把最小的挑出来放在第一个位置, 然后把次小的挑出来放在第二个位置, ……, 这样不就得了, 没错, 就是这么简单.

Time Complexity O(n^2), 无论最好还是最坏.

2. 冒泡排序(Bubble Sort)

void BubbleSort(int *a, int n)
{
     for(int i=0; i<n;i++)
         for(int j=0; j<n-i-1; j++)
             if(a[j]>a[j+1]) swap(&a[j], &a[j+1]);
 }

主要思想是: 每次两两比较, 把如果左边比右边大, 那么就交换位置, 如果小就不变, 这样第一遍之后最右边就是最大的数, 第二遍之后右边第二个就是次大的数, 做了n遍就结束了.
Time Complexity O(n^2), 而且不论输入的数组情况是怎么样的, 都是n^2.

3. Insertion Sort(插入排序)

void InsertSort(int* a, int n)
{
        int temp;
        for(int i =1; i<n; i++)
        {        temp = a[i];
           for(int j=i-1; j>=0&&temp<a[j];j--)
                a[j+1] = a[j];
         a[j+1] = temp;
}

Insertion Sort的主要思想在于假设我们每次面对的都是一个已经排好序的数列, 然后我们把需要加进去的元素插入在里面就好了, 如果联系到生活中很像我们打扑克牌时候的插牌方法(当然至少我是这样插牌的..), 可以很容易发现平均时间复杂度是O(n^2), 但是如果遇到数列已经排好序的情况, 那复杂度就变成了O(n), 这是最优情况.

4. MergeSort

int* MergeSort(int *a, int n)
{
   if(n<=0) return;
   elseif(n==1)
   {
     int* temp = malloc(sizeof(int)*1);  //I always forget this line!
     temp[0] = a[0];
     return temp;
    }
   int n1 = n/2;

   int* temp1 = MergeSort(a, n1);
   int* temp2 = MergeSort(a+n1, n-n1);

   int* temp = (int *)malloc(sizeof(int)*n);
   int i=0, j=0, k =0;
   while(i<n1||j<(n-n1))
   	{
   	   if(i==n1)
   	     temp[k++] = temp2[j++];
   	   elseif (j==(n-n1))
   	     temp[k++] = temp1[i++];
   	   else
   	     temp[k++] = (temp1[i]<temp2[j] ? temp1[i++]:temp2[j++]);
          //I like this line, it rocks
   	 }
   free(temp1);
   free(temp2);
   return temp;
}

主要的思想是divide and conquer, 每次把数组平均分成两个部分, 然后分别排序, 然后再combine起来, 时间复杂度的计算 T(n) = 2T(n/2) + O(n), T(n) = O(nlogn), 所有情况都是这样.

MergeSort的坏处在于, 它不是in-place的, 意思是就是它不能在原数组上做好, 需要额外的空间, (就是我的code里面的那些malloc, free阿这种),
但是它的好处就是它在所有的情况都是O(nlogn)的时间复杂度, 尤其在了解到O(nlogn)是排序时间复杂度的理论下限之后, 我们可以发现这个性质是多么宝贵.

而且从MergeSort中还能推出另一个性质, 求一个数组的逆序是多少?

5. QuickSort

void QuickSort(int *a, int n)
{
if(n>2)
{
	int index = Partition(a, n);
	QuickSort(a, index);
	QuickSort(a+index+1, n-index-1);
}
}

int Partition(int *a, int n)
{
   int pivot = a[0];
   int i=1, j=1;
   while(j<n)
   {
      if(a[j]<pivot) swap(&a[j], &a[i++]);
      j++;
   }
   swap(&a[i-1], &a[0]);
   return i-1;
}

QuickSort, 顾名思义, 快速排序就是很快拉, 平均时间复杂度是O(nlogn), 然后最坏情况就是已经排好序的时候, O(n^2), (所以有人说如果你要测试一个排序程序的话, 一个很好的方法就是把一组排好序的数组作为输入序列 :)).

它所带的partition函数, 实在很屌, 可以附带出很多副产品.