常见排序详解

1、常见的算法>排序算法

插入排序：直接插入排序、希尔排序；

选择排序：选择排序、堆排序；

交换排序：冒泡排序、快速排序；

归并排序：归并排序；

2、常见算法>排序算法的实现

2.1 插入排序

2.1.1 直接插入排序

当插入第 i（>=1）个元素是，前面的 i-1 个元素都已经排序好了，此时将第 i 个元素与前 i-1 个元素进行比较，找到对应的位置插入即可，原来位置上的元素向后移动即可。

//打印
void PrintArray(int* a, int n)
{int i = 0;for ( i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}//直接插入排序
//升序
//最坏：O(N^2)  逆序
//最好：O(N)    顺序有序
void InsertSort(int* a, int n)
{for (int i = 0; i < n; i++){int end = i - 1;int tmp = a[i];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}a[end + 1] = tmp;}}
}void TestInsertSort()
{int a[] = { 3,6,9,8,4,7,5,1,2,0 };PrintArray(a, sizeof(a) / sizeof(a[0]));InsertSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}int main()
{TestInsertSort();return 0;
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入算法>排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的算法>排序算法

4. 稳定性：稳定

2.1.2 希尔排序（缩小增量法）

思想：把待排序数据分为gap组，所有距离为gap的为一组，然后针对每组进行排序，再将gap进行减小，重复上述分组和排序的工作，当gap=1时，数据就已经排好了。

//希尔排序
void ShellSort(int* a, int n)
{int gap = n;while (gap>1){gap /= 2;//for (int i = gap; i < n; i++)//{//    int end = i - gap;//    int tmp = a[i];//    while (end >= 0)//    {//        if (tmp < a[end])//        {//            a[end + gap] = a[end];//            end -= gap;//        }//        else//        {//            break;//        }//        a[end + gap] = tmp;//    }//}for (int i = 0; i < n-gap; i++){int end = i;int tmp = a[i+gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}PrintArray(a, n);}
}void TestInsertSort()
{int a[] = { 3,6,9,8,4,7,5,1,2,0 };PrintArray(a, sizeof(a) / sizeof(a[0]));ShellSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));}int main()
{TestInsertSort();return 0;
}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定 O(N^1.3)

2.2 选择排序

2.2.1直接选择排序

思想：首先在未排序序列中找到最小（大）元素，分别存放到序列的起始位置。再从剩

余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的起始位置。重复第二步，直到所有元素均排序完毕。

优化：一次找两个，在未排序序列中，寻找到最大的和最小的数据，记下来，然后最小的和当前序列起始位置互换，最大的和当前序列末尾位置互换。重复此过程，最后得到的也是一个升序序列。

特别情况：当最大值=当前序列的起始位置，那么交换完最小的数据和当前序列首位的数据之后，改变记录最大的数据下标的变量，让它变成正确的。

void Swap(int* p1,int* p2)
{int tmp=*p1;*p2=*p1;*p1=tmp;
}void SelectSort(int* a,int n)
{int left=0,right=n-1;while(left<right){int mini=left,maxi=right;for(int i=left+1;i<=right;i++){if(a[i]<a[mini]){mini=i;            }        if(a[i]>a[maxi]){maxi=i;            }}Swap(&a[left],&a[mini]);if(left=maxi){maxi=mini;        }    Swap(&a[right],&a[maxi]);left++;right--;}
}

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

2.2.2 堆排序

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//选出左右孩子中大的那个if (child + 1 < n && a[child] < a[child + 1]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{//建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

堆排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

2.3 交换排序

2.3.1 冒泡排序

思想：每次比较相邻的两个元素，假设有N个数据，需要升序排序，那么就要冒泡N-1次，每一次都把当前序列的最大值放到最后的位置，最后剩下的那个数据不需要冒泡，因为它就是最小的。

// 最坏：O(N^2)
// 最好：O(N)
//冒泡排序
void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){bool exchange = false;for (int j = 0; j < n - 1 - i; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);exchange = true;}}if (exchange == false){return;}}return;
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

2.3.2 快速排序

思想：任取待排序元素序列中的某元素作为基准值（key），按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

key一般选择最左边的数字，但是，当要排序的数据是升序/降序时，就会出现一直是左边/右边部分在递归，这样就会增加空间复杂度，递归的层数太多可能会栈溢出，影响效率。

优化：使用随机值取key法或者三数取中。

注意：key值如果选择左边那就要让右边先走，选在右边就要先让左边先走。

1、hoare法

//三数取中
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}//Hoare
int PartSort1(int* a, int left, int right)
{随机选keyi//int randi = left+ rand() % (right - left);//Swap(&a[randi], &a[left]);//三数取中int midi = GetMidNumi(a, left, right);if (midi != left){Swap(&a[left], &a[midi]);}int keyi = left;while (left < right){//右边找小while (left < right && a[right] >= a[keyi]){right--;}//左边找大while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;return keyi;
}void QuickSort(int* a, int left, int right)
{//递归结束条件if (left >= right){return;}int keyi = PartSort1(a,left,right);//递归// [begin, keyi-1] keyi [keyi+1, end] QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}void TestQuickSort()
{int a[] = { 9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-3,-4,-5,-5,-6,-7,-8,-9 };PrintArray(a, sizeof(a) / sizeof(int));QuickSort(a, 0, sizeof(a) / sizeof(int)-1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}

2、挖坑法

//三数取中
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}//挖坑法
int PartSort2(int* a, int left, int right)
{随机选keyi//int randi = left+ rand() % (right - left);//Swap(&a[randi], &a[left]);//三数取中int midi = GetMidNumi(a, left, right);if (midi != left){Swap(&a[left], &a[midi]);}int key = a[left];int hole = left;while (left < right){//右边找小while (left < right && a[right] >= key){right--;}a[hole] = a[right];hole = right;//左边找大while (left < right && a[left] <= key){left++;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;//下标
}void QuickSort(int* a, int left, int right)
{//递归结束条件if (left >= right){return;}int keyi = PartSort2(a,left,right);//递归// [begin, keyi-1] keyi [keyi+1, end] QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}void TestQuickSort()
{int a[] = { 9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-3,-4,-5,-5,-6,-7,-8,-9 };PrintArray(a, sizeof(a) / sizeof(int));QuickSort(a, 0, sizeof(a) / sizeof(int)-1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}

3、前后指针法（推荐）

//三数取中
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}//前后指针
int PartSort3(int* a, int left, int right)
{随机选keyi//int randi = left+ rand() % (right - left);//Swap(&a[randi], &a[left]);//三数取中int midi = GetMidNumi(a, left, right);if (midi != left){Swap(&a[left], &a[midi]);}int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}void QuickSort(int* a, int left, int right)
{//递归结束条件if (left >= right){return;}int keyi = PartSort1(a,left,right);//递归// [begin, keyi-1] keyi [keyi+1, end] QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}void QuickSort(int* a, int left, int right)
{//递归结束条件if (left >= right){return;}//小区间优化--当递归到一定的层次，就使用插入排序if ((right - left + 1) > 10){int keyi = PartSort3(a, left, right);//递归// [left, keyi-1] keyi [keyi+1, right] QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}else{InsertSort(a + left, right - left + 1);}
}//非递归
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort3(a, begin, end);// [begin,keyi-1] keyi [keyi+1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi+1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}void TestQuickSort()
{int a[] = { 9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-3,-4,-5,-5,-6,-7,-8,-9 };PrintArray(a, sizeof(a) / sizeof(int));QuickSort(a, 0, sizeof(a) / sizeof(int)-1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

2.4 归并排序（保证左右两组是有序的）

基本思想：直接将给定数据分为两组，设置两指针分别指向两组数据的第一个，然后比较这两个数据，数据小的（假设排升序）放到一个新的数组里，同时指针向后+1。一直循环，直到某一组结束，再将另一组未完成的数据放入新数组里，最后再将得到的新数组拷贝到原来的数组里。两个组别里面的数组必须是有序且是同样的顺序。

那么对于一个乱序数组，要使用归并排序排成有序数组，就不能保证向上面一样，直接分成两组是有序的，那么就要细分下去，直到分出的两组里面，每一组都只有一个数据，一个数据自然是有序的，这种分下去的思想叫做“分治”。

分治完成后再一层层的往上合并，最后就可以得到有序的数据。

2.4.1 递归

//归并排序
//递归
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end){return;}int mid = (begin + end) / 2;// [begin, mid] [mid+1,end]，子区间递归排序_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);//[begin, mid] [mid+1,end]，子区间归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}//归并排序
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort::malloc");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

2.4.2 非递归

基本思想：将递归改成循环，直接从每一小组只有一个元素的情况开始归并排序，那就是非递归法。

但是，非递归法也存在一些问题。比如，不能保证每一次都可以凑齐要归并排序的两组数据。在单个数据为一组的情况下，前面的归并没有问题，但是单个数据为一组的就没有其他数据与他归并，这时再按照之前的边界去访问数据就会出现越界的情况。

//归并排序--非递归
//void MergeSortNonR(int* a, int n)
//{
//    int* tmp = (int*)malloc(sizeof(int) * n);
//    if (tmp == NULL)
//    {
//        perror("MergeSortNonR::malloc");
//        return;
//    }
//
//    int gap = 1;
//    while (gap < n)
//    {
//        for (int i = 0; i < n; i += gap * 2)
//        {
//            int begin1 = i, end1 = i + gap - 1;
//            int begin2 = i + gap, end2 = i + gap * 2 - 1;
//
//            //end1越界,不归并了
//            //end1没越界，begin2越界，不归并了
//            if (end1 >= n || begin2 >= n)
//            {
//                break;
//            }
//            //end1、begin2没有越界，end2越界,修正
//            if (end2 >= n)
//            {
//                end2 = n - 1;
//            }
//
//            printf("[%d, %d][%d, %d]", begin1, end1, begin2, end2);
//
//            int j = i;
//            while (begin1 <= end1 && begin2 <= end2)
//            {
//                if (a[begin1] < a[begin2])
//                {
//                    tmp[j++] = a[begin1++];
//                }
//                else
//                {
//                    tmp[j++] = a[begin2++];
//                }
//            }
//
//            while (begin1 <= end1)
//            {
//                tmp[j++] = a[begin1++];
//            }
//
//            while (begin2 <= end2)
//            {
//                tmp[j++] = a[begin2++];
//            }
//
//            //归并一部分拷贝一部分
//            memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
//        }
//        printf("\n");
//        gap *= 2;
//    }
//    free(tmp);
//}void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSortNonR::malloc");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;//修正路线if (end1 >= n || begin2 >= n){end1 = n - 1;//制造一个不存在的区间，这样就不会满足下面的begin2<=end2的条件begin2 = n;end2 = n - 1;}//end1、begin2没有越界，end2越界,修正if (end2 >= n){end2 = n - 1;}printf("[%d, %d][%d, %d]", begin1, end1, begin2, end2);int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//归并一部分拷贝一部分}// 间距为gap的多组数据，归并完以后，一把拷贝(梭哈)memcpy(a, tmp, sizeof(int) * n);printf("\n");gap *= 2;}free(tmp);
}void TestMergeSortNonR()
{int a[] = { 9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-3,-4,-5,-5,-6,-7,-8,-9 };PrintArray(a, sizeof(a) / sizeof(int));MergeSortNonR(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestMergeSortNonR();return 0;
}

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(N)

4. 稳定性：稳定

2.5 非比较排序

计数排序：（相对位置映射计数）

1、统计相同元素出现的次数；

2、根据统计的结果将序列回收到原来的序列中；

//计数排序
// 时间复杂度：O(N+range)--range:开辟空间的数据个数
// 空间复杂度：O(range)
void CountSort(int* a, int n)
{int max = a[0], min = a[0];for (int i = 0; i < n; i++){if (a[i] > max){max = a[i];}if (a[i]<min){min = a[i];}}int range = max - min + 1;int* countA = (int*)malloc(sizeof(int) * range);if (countA == NULL){perror("CountSort::malloc");return;}memset(countA, 0, sizeof(int) * range);//计数for (int i = 0; i < n; i++){countA[a[i] - min]++;}//排序int j = 0;for (int i = 0; i < range; i++){while (countA[i]--){a[j++] = i + min;}}free(countA);
}void TestCountSort()
{int a[] = { 9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-3,-4,-5,-5,-6,-7,-8,-9 };PrintArray(a, sizeof(a) / sizeof(int));CountSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestCountSort();return 0;
}

计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

2. 时间复杂度：O(MAX(N,范围))

3. 空间复杂度：O(范围)

4. 稳定性：稳定

计数排序适合范围集中，且范围不大的整形数组排序。不适合范围分散或者非整形的排序，如：字符串、浮点数等。

3.算法>排序算法复杂度及稳定性

稳定性：假定在待排序的记录序列中，存在多个相同的关键字的记录，若经过排序，这些记录的相对次序报吃不变，即在原序列中，r [ i ] = r [ j ] ，且r [ i ] 在 r [ j ] 之前，而在排序后的序列中，r [ i ] 仍在 r [ j ] 之前，则这种算法>排序算法时稳定的，否则称为不稳定的。

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O（n^2）	O（n）	O（n^2）	O（1）	稳定
简单选择排序	O（n^2）	O（n^2）	O（n^2）	O（1）	不稳定
直接插入排序	O（n^2）	O（n）	O（n^2）	O（1）	稳定
希尔排序	O（nlogn）~O（n^2）	O（n^1.3）	O（n^2）	O（1）	不稳定
堆排序	O（nlogn）	O（nlogn）	O（nlogn）	O（1）	不稳定
归并排序	O（nlogn）	O（nlogn）	O（nlogn）	O（n）	稳定
快速排序	O（nlogn）	O（nlogn）	O（n^2）	O（nlogn）~O（n）	不稳定