学步园

排序分为内部排序和外部排序，内部排序是指待排序的数据都是在内存中的，例如数组；外部排序指待排序资源在内存外，例如对文件的排序。此篇说的是内部排序。通俗地来说，内部排序就是将一堆数据按一定规则对它进行排序。排序又分为稳定排序和不稳定的排序，如果初始序列Ai，Ak有序（Ai ＝ Ak），排序后变成了Ak，Ai，称为不稳定排序。下面介绍几个经典常见的排序。（以下排序都是以数组为例进行排序）

1.选择排序

思路就是每次从待排序列取出最大或最小的值的元素，插入到以有序的序列后边。

 void select_sort(int A[], int n){
     cout << "select sort" << endl;
     int min, k;
     for(int i = 0; i < n - 1; i++){
         min = A[k = i];
         for(int j = i + 1; j < n; j++)
             if(min > A[j])
                 min = A[k = j];
 
         A[k] = A[i];
         A[i] = min;
     }
 }

2.直接插入排序

从待排序列中遍历元素（不需要做对比，直接从取第一个元素即可），将选中元素按顺序插入到以排序的序列中。

void insert_sort(int A[], int n){
     cout << "insert sort" << endl;
     int tmp, j;
     for(int i = 1; i < n; i++){
         tmp = A[i];
         if(A[i] < A[i-1]){
             j = i;
             while(j > 0 && A[j - 1] > tmp){
                 A[j] = A[j - 1];
                 j--;
             }
             A[j] = tmp;
         }
     }
 }

3.冒泡排序

简单的说就是前后两个元素依次比较，如果不符合，就交换两者。每一趟排序，可以排出一个最大或最小的元素，依次冒泡就可以做出排序。通常需要n－1趟排序，可以优化一下，用一个标记变量来检测，如果一趟排序中没有元素进行过交换，说明当前序列已经有序了，不需要在交换了。

void bubble_sort(int A[], int n){
     bool check; 
     int tmp;
     for(int i = 0; i < n; i++){
         check = true; 
         for(int j = 0; j < n - 1 - i; j++){
             if(A[j] > A[j + 1]){
                 tmp = A[j];
                 A[j] = A[j + 1];
                 A[j + 1] = tmp;
                 check = false;
             }
         }
         if(check)
             break;
     }
 }

4.希尔排序

希尔排序是将待排序列按照某一个增量分为若干个子序列，依次对子序列进行插入排序，让待排序列部分有序，然后将增量递分为更多的子序列，在做上述排序，直到增量为1.增量的选择是依次递减的，增量选择的好坏关系到时间复杂度，此处选择折半递减。下面看图文讲解。

void shell_insert(int A[], int d, int n){
     int tmp, j; 
     for(int i = d; i < n; i++){
         tmp = A[i];
         j = i - d;
         while(j >= 0 && A[j] > tmp){
             A[j + d] = A[j];
             j -= d;
         }
         if(j != i - d)
             A[j + d] = tmp;
     }
 }   
 
 void shell_sort(int A[], int n){
     int d = n / 2;
     while(d >= 1){
         shell_insert(A, d, n);
         d /= 2;
     }
}

5.归并排序

思路是将待排序列，例如有n个记录，可以将它们看成是n个有序的子序列，对其两两进行排序，然后合并成n/2个有序的子序列，再依次两两合并，直到最后剩下一个有序序列，排序完成。

void Merge(int A[], int B[], int s, int m, int t){
     int i,j,k;
     for(i = m + 1, j = s; s <= m && i <= t; j++){
         if(A[s] < A[i])
             B[j] = A[s++];
         else
             B[j] = A[i++];
     }   
             
     if(s <= m){
         for(k = 0; k <= m - s; k++)
             B[j + k] = A[s + k];
     }
             
     if(i <= t)
         for(k = 0; k <= t - i; k++)
             B[j + k] = A[i + k]; 
 }

 void MSort(int A[], int B[], int s, int e){
     int m;
     int tmp[100];
     if(s == e) 
         B[s] = A[s];
     else{
         m = (s + e) / 2;
         MSort(A, tmp, s, m);
         MSort(A, tmp, m + 1, e);
         Merge(tmp, B, s, m, e);
     }   
 }

堆排序,

快速排序

各种排序比较