首页 > > 程序设计 > C/C++ >

常用排序算法

2019-01-03 09:55:24来源：博客园阅读 ()

插入排序

非常简单的排序算法，时间复杂度为O(n²)，是稳定的排序算法

 1 void insertsort(int a[], int n) {
 2     for (int i = 2; i <= n; i++) {
 3         if (a[i] < a[i - 1]){
 4             a[0] = a[i];
 5             a[i] = a[i - 1];
 6             int j;
 7             for (j = i - 2; a[j] > a[0]; j--) //比a[0]大的都要往后移
 8                 a[j + 1] = a[j];
 9             a[j + 1] = a[0]; //边界可以这么考虑，假设j=0了，也就是a[0]最小，那么它应该放在a[1]处，也就是a[j+1]
10         }
11     }
12 }

希尔排序

希尔排序是直接插入排序的一种改进算法，按照不同步长对元素进行插入排序，其时间复杂度与步长的选取有关，小于O(n²) ，如何选取步长增量序列是一个数学难题，当今还无人解决，是一种不稳定排序算法。

 1 void shell(int a[], int n) {
 2     int gap = n / 2;
 3     while (gap >= 1) { // gap=1结束
 4         for (int i = gap + 1; i <= n; i++) { // i=gap+1，从第一组的第二个元素开始往前插入排序
 5             if (a[i] < a[i - gap]) {
 6                 a[0] = a[i];
 7                 a[i] = a[i - gap];
 8                 int j;
 9                 for (j = i - gap ; j > 0 && a[j] > a[0]; j = j - gap) //比a[0]大的都要往后移动  j>0 这个条件很关键 否则容易越界，因为与直接插入排序不同
10                     a[j + gap] = a[j];
11                 a[j + gap] = a[0];
12             }
13         }
14         gap /= 2;
15     }
16 }

冒泡排序

冒泡排序比较简单粗暴，其时间复杂度为O(n²) ，是一种稳定的排序算法，两两元素互相比较并交换，每一趟选出最大的一个放在末尾。

 1 void bubble(int a[], int n)
 2 {
 3     for (int i = 1; i < n; i++) //n-1趟
 4         for (int j = 1; j < n - i + 1; j++) 
 5             if (a[j] > a[j + 1]){
 6                 int temp = a[j];
 7                 a[j] = a[j + 1];
 8                 a[j + 1] = temp;
 9             }
10 }

快速排序

快速排序是目前被认为最好的一种排序方法，平均情况下快速排序的时间复杂度是Θ(nlogn)，最坏情况是Θ(n^2)。当划分产生的两个子问题分别包含 n-1 和 0 个元素时，最坏情况发生。划分操作的时间复杂度为Θ(n)，T(0)=Θ(1)，这时算法运行时间的递归式为 T(n)=T(n?1)+T(0)+Θ(n)=T(n?1)+Θ(n)，解为T(n)=Θ(n2)。当划分产生的两个子问题分别包含?n/2?和?n/2??1个元素时，最好情况发生。算法运行时间递归式为 T(n)=2T(n/2)+Θ(n)，解为T(n)=Θ(nlgn)。事实上只要划分是常数比例的，算法的运行时间总是O(nlgn)。假设按照 9:1 划分，每层代价最多为 cn，递归深度为 log10/9n=Θ(lgn)，故排序的总代价为 O(nlgn)。

int Partition(int a[], int low, int high) { //这个函数是用来划分的
    a[0] = a[low]; // a[0]是用来暂存 枢轴 的 所以数组从 1 开始到 10;
    int pivotloc = a[low];
    while (low < high) {   //长度为1就不需要划分了
        while (low < high && a[high] >= pivotloc) --high;    //a[high]大于等于枢轴才能往前移动
        a[low] = a[high];
        while (low < high && a[low] <= pivotloc) ++low;      //a[low]小于等于枢轴才能往后移动
        a[high] = a[low];
    }
    a[low] = a[0]; //这句别漏了 枢轴要填回去
    return low;
}
void Qsort(int a[], int low, int high) {
    if (low < high) {  //这句别漏了  递归出口
        int pivotloc;
        pivotloc = Partition(a, low, high);  //比pivotloc小的放左边 大的放右边
        Qsort(a, low, pivotloc - 1);         //递归排序左边  中间的pivotloc就不用排了 是枢轴
        Qsort(a, pivotloc + 1, high);        //递归排序右边 
    }
}
void QuickSort(int a[], int n) {
    Qsort(a, 1, n); //数组从1开始到n结束
}