排序2（万字详细版）

一快速排序

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为⽌。

快速排序也分为三个常用的，分别是hoare版本，挖坑法，lomuto前后指针。

1.1 hoare版本

算法思路：

1）创建左右指针，确定基准值

2）从右向左找出⽐基准值⼩的数据，从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次循环

问题1：为什么跳出循环后right位置的值⼀定不⼤于key？

当 left > right 时，即right⾛到left的左侧，⽽left扫描过的数据均不⼤于key，因此right此时指

向的数据⼀定不⼤于key。

先看第二个函数，基本思路就是每次找到基准值，然后再左右递归直至出现left>right的情况。

我们来拿这个数组来试一下。

首先先让right找到比key小的，就是3，再让left找到比key大的。

此时left<right，交换就得到下面这个数组了，让left++和right--

然后right在移动，left再移动。

此时right<left，出循环了，此时让arr[right]和arr[key]位置的值交换一下，此时就找到基准值的位置了。

然后再返回到另外一个函数中继续执行这个，进行递归调用，每次都是通过这种方法找到每一部分的基准值，进行对它们的调整。

swap(&arr[left++],&arr[right--]);这个语句中的++和--可以不写吗？答案是不可以，因为如果一个无序数组全是2 2 2 2 的时候，此时left和right都不会移动了，此时就陷入了死循环，还有上面的必须严格大于arr[key]才能交换，否则时间复杂度可能达到o（n的平方）。

1.2 挖坑法

思路：

创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新

的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）。

我们还用这个图来讲解一下吧。

此时我们先让坑位hole指向left，key的作用是存储开始坑位的值的，首先我们要先让right移动，找到比key小的值。

找到了3比key要小，所以直接让3把原来的坑位给覆盖掉，此时就实现了小的元素在左边了，再让right位置重新生成坑位，然后left开始找到比key大的。

此时发现没找到就出了循环，然后再让坑位等于key即可，此时把hole返回。

现在我们有几个问题来解决一下，为什么开始的时候不能让left++呢？

我们可以拿这个例子来看一下，如果直接让left++的话，此时在3的位置就会停下来，此时right和left都指向3那个位置，此时再执行下面的语句的话，此时我们就用3把1给覆盖了，然后hole指向3的位置，此时出去循环又执行了arr[hole]=key这个语句了，此时就出现了问题，发现基准值1的左边有比1大的数，此时就出现了问题，如果不++的话，就没有这个问题了。

还有第二个问题，为什么left=right也要停止呢？

还用上面那个，如果left=right还不停止，此时right=-1了，此时让arr[hole]=arr[right]，就会出现数组越界了。

这里的arr[right]和arr[left]为什么都要有=呢，单纯大于或者小于key不行吗？

答案是不行的，我现在举个简单的例子。

让我们对这一个数组来排序，如果仅仅大于或者小于的话，此时就无法进入到right--和left++那个循环之中，此时整个系统就陷入了死循环了。

1.3 双指针法

这个是通过两个指针来寻找，一个cur去前面探路，找到比基准值小的，找到之后我们要判断这个++prev是否等于cur，如果等于先不交换，因为防止做一些不必要的交换，我们主要就是让小的在基准值前面就行了，cur>right的时候，说明此时已经找完了，此时prev指向的一定是最后一个小于基准值的数据，然后和基准值交换一下就完成了。

我们来通过下图来讲解一下。

我们现在这个图就可以很好解释++prev为什么不能等于cur了，我们来移动一下。

这里发现1就符合，但是++prev此时和cur相等，不能交换，如果此时交换，发现2也要交换，此时效率就会很低，如果是一个降序的，那么此时时间复杂度就会达到o（n的平方）了，效率很低，所以我们要限制一下，接下来我们继续移动。

这时候，我们发现此时大于了基准值了，此时只让cur移动。

找到下一个比基准值小的，此时++prev！=cur了，此时就要交换了，此时prev还是要执行++，此时就指向了7的位置，直接就把小的换到前面了，大的就去后面了，然后再继续进行这个过程，最后就完成了排序。

二 . 归并排序

归并排序算法思想：

归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divide and Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个

⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。归并排序核⼼步骤：

这个排序的思想就是通过把一个无序的数组给分解，一直分解到不能再分解，然后再进行比较排序，逐渐合并的过程。

代码实现：

我们先看一下这个过程，一直分解把一个数组分解剩下一个元素，也就是left=right的时候。

此时我们先看左边，此时分解完成了，此时begin1和end1都指向6，begin2和end2都指向了10的位置，此时我们就要比较6和10的大小进行排序，此时把数据存入到tmp数组中，下面的两个while语句是防止哪个序列中的元素没有完全放入数组中，最后的for循环是吧tmp数组中的内容拷贝给arr数组。

此时执行完了这次函数栈帧的代码了，此时就会返回到上一层，再执行右边的递归然后把1和7完成了排序，此时返回到上一层函数栈帧了此时begin1就指向了6，end1指向了10，begin2指向了1，end2指向了7，此时就要排这几个的序列了，发现是1 2 7 10的序列，再次返回到上层函数栈帧，再对右边的序列进行递归，循环这个过程最终就会完成了排序了。

三 . 非比较排序

计数排序

计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。操作步骤：

1）统计相同元素出现次数

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

这个就是把相应的数放在他所对应的下标处，让这个下标++，表示数的数量，然后再对它进行打印。

但是现在又有了一个问题，如果我们的数是{100 ， 101 ， 110}类似于这样的数据，我们说的是要把它们放在对应的下标下面，但是这个难道要创建到下标为110的吗，如果这样的话，前面的100个位置不久荒废了吗，造成了极大的空间浪费，我们应该怎么解决呢？

我来提出一个想法，我们只开辟max-min+1个空间大小的数组即可，让第0个位置存放min的位置，中间存放中间数据，max-min+1的位置存放最大的那个数据即可，此时我们上面那个数组只需要开辟110-100+1个位置即可，此时0的位置可以放100，1的位置放101，以此类推最后一个10的位置就放110了，我们只需要开辟11个空间，极大的节约了空间。

这样我们就完成了代码的编写了，我们首先要找到最大值和最小值，为count数组分配指定的空间，然后再次遍历我们的数组，让其值所在的对应位置++，统计每个值的数量，此时我们就完成了100放在0处，110放在10处了，统计完成数量之后，我们再次进入循环，此时i要小于range，此时我们要遍历count数组了，此时较小的值就放在的下标比较小的位置了，此时我们再次通过一个while循环，把它们的值放入我们的arr数组中，此时它们的值正好就是等于i+min的值的，此时通过while循环控制放入的数量，此时就完成了排序。

四. 算法时间效率的比较

void TestOP()
{
   srand(time(0));
   const int N = 100000;
   int* a1 = (int*)malloc(sizeof(int) * N);
   int* a2 = (int*)malloc(sizeof(int) * N);
   int* a3 = (int*)malloc(sizeof(int) * N);
   int* a4 = (int*)malloc(sizeof(int) * N);
   int* a5 = (int*)malloc(sizeof(int) * N);
   int* a6 = (int*)malloc(sizeof(int) * N);
   int* a7 = (int*)malloc(sizeof(int) * N);
int* a8 = (int*)malloc(sizeof(int)* N);
int* a9 =(int*)malloc(sizeof(int)*N);
int* a10=(int*)malloc(sizeof(int)*N);
   for (int i = 0; i < N; ++i)
   {
       a1[i] = rand();
       a2[i] = a1[i];
       a3[i] = a1[i];
       a4[i] = a1[i];
       a5[i] = a1[i];
       a6[i] = a1[i];
       a7[i] = a1[i];
       a8[i] = a1[i];
       a9[i]=a1[i];
   }
   int begin1 = clock();
   InsertSort(a1, N);
   int end1 = clock();

   int begin2 = clock();
   ShellSort(a2, N);
   int end2 = clock();
   int begin3 = clock();
   SeclectSort(a3, N);
   int end3 = clock();
   int begin4 = clock();
   HeapSort(a4, N);
   int end4 = clock();

   int begin5 = clock();
   QuickSort(a5, 0, N-1);
   int end5 = clock();
   int begin6 = clock();
   MergeSort(a6, N);
   int end6 = clock();
   int begin7 = clock();
   BubbleSort(a7, N);
   int end7 = clock();
   int begin8=clock();
   QuickSort2(a8,0,N-1);
   int end8=clock();
   int begin9=clock();
   QuickSort3(a9,0,N-1);
   int end9=clock();
   int begin10=clock();
   CountSort(a10 ,N);
   int end10=clock();
   printf("InsertSort:%d ms\n", end1 - begin1);
   printf("ShellSort:%d ms\n", end2 - begin2);
   printf("SelectSort:%d ms\n", end3 - begin3);
   printf("HeapSort:%d ms\n", end4 - begin4);
   printf("horeQuickSort:%d ms\n", end5 - begin5);
   printf("MergeSort:%d ms\n", end6 - begin6);
   printf("BubbleSort:%d ms\n", end7 - begin7);
   printf("wa keng QuickSort:%d ms\n", end8 - begin8);
   printf("QucickSort3:%d ms\n", end9 - begin9);
   printf("CountSort:%d ms\n", end10 - begin10);
   free(a1);
   free(a2);
   free(a3);
   free(a4);
   free(a5);
   free(a6);
   free(a7);
   free(a8);
   free(a9);
   free(a10);
}

代码太长了，我就不截图了，此时我们可以用这个代码可以清晰的看到算法时间效率的差异

如图所示，发现同时处理100000条数据的时候希尔排序，堆排序，三种快排和归并排序和非比较排序的效率是比较高的。

五.源代码

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
//╤яеепР
void swap(int* a,int* b){
int temp=*a;
*a=*b;
*b=temp;
}
void AdjustDown(int* arr,int parent,int n){
int child=parent*2+1;
while(child<n){
if(child+1<n&&arr[child]<arr[child+1]){
child++;
}
if(arr[parent]<arr[child]){
swap(&arr[parent],&arr[child]);
parent=child;
child=parent*2+1;
}
else{
break;
}
}
}
void HeapSort(int* arr,int n){
for(int i=(n-1-1)/2;i>=0;i--){
AdjustDown(arr,i,n);
}
int end=n-1;
while(end>0){
swap(&arr[0],&arr[end]);
AdjustDown(arr,0,end);
end--;
}
}
void InsertSort(int* arr,int n){
for(int i=0;i<n-1;i++){
int end=i;
int tmp=arr[end+1];
while(end>=0){
if(arr[end]>tmp){
arr[end+1]=arr[end];
end--;
}
else{
break;
}
}
arr[end+1]=tmp;
}
}
//оё╤ШеепР
void ShellSort(int* arr, int n){
int gap=n;
while(gap>1){
gap=gap/3+1;
for(int i=0;i<n-gap;i++){
int end=i;
int tmp=arr[end+gap];
while(end>=0){
if(arr[end]>tmp){
arr[end+gap]=arr[end];
end-=gap;
}
else{
break;
}
}
arr[end+gap]=tmp;
}
}
}
void BubbleSort(int* arr,int n){
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void SeclectSort(int* arr,int n){
int begin=0,end=n-1;
while(begin<end){
int min=begin,max=begin;
for(int i=begin+1;i<=end;i++){
if(arr[min]>arr[i]){
min=i;
}
if(arr[max]<arr[i]){
max=i;
}
}
if(max==begin){
max=min;
}
swap(&arr[min],&arr[begin]);
swap(&arr[max],&arr[end]);
begin++;
end--;
}
}
//双指针法快排
int _QuickSort3(int* arr,int left,int right){
int prev=left,cur=left+1;
int key=left;
while(cur<=right){
if(arr[cur]<arr[key]&&++prev!=cur){
swap(&arr[prev],&arr[cur]);
}
++cur;
}
swap(&arr[prev],&arr[key]);
return prev;
}
void QuickSort3(int* arr,int left,int right){
if(left>right){
return;
}
int key=_QuickSort3(arr,left,right);
QuickSort3(arr,left,key-1);
QuickSort3(arr,key+1,right);
}
//挖坑法
int _QuickSort2(int* arr, int left, int right)
{
   int hole = left;
   int key = arr[hole];
   //left++;

   while (left < right)
   {
       while (left < right && arr[right] >= key)
       {
           right--;
       }
       arr[hole] = arr[right];
       hole = right;
       while (left < right && arr[left] <= key)
       {
           left++;
       }
       arr[hole] = arr[left];
       hole = left;
   }
   arr[hole] = key;
   return hole;
}
void QuickSort2(int* arr,int left,int right){
if(left>=right){
return;
}
int key=_QuickSort2(arr,left,right);
QuickSort2(arr,left,key-1);
QuickSort2(arr,key+1,right);
}
//霍尔快排
int _QuickSort(int* arr, int left, int right)
{
int key=left;
++left;
while(left<=right){
while(left<=right&&arr[right]>arr[key]){
right--;
}
while(left<=right&&arr[left]<arr[key]){
left++;
}
if(left<=right){
swap(&arr[left++],&arr[right--]);
}
}
swap(&arr[right],&arr[key]);
return right;
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
   if(left>=right){
return;
   }
   int key=_QuickSort(arr,left,right);
   QuickSort(arr,left,key-1);
   QuickSort(arr,key+1,right);
}
//归并排序
void _MergeSort(int* arr, int left, int right,int* tmp)
{
   if (left >= right)
   {
       return;
   }
   int mid = (left + right) / 2;
   //根据mid划分成两个序列：[left,mid] [mid+1,right]
   _MergeSort(arr, left, mid,tmp);
   _MergeSort(arr, mid + 1, right,tmp);

   //合并[left,mid] [mid+1,right]
   int begin1 = left, end1 = mid;
   int begin2 = mid + 1, end2 = right;
   int index = begin1;
   while (begin1 <= end1 && begin2 <= end2)
   {
       if (arr[begin1] < arr[begin2])
       {
           tmp[index++] = arr[begin1++];
       }
       else {
           tmp[index++] = arr[begin2++];
       }
   }
   //可能存在第一个序列中的数据没有全部放到tmp中
   //可能存在第二个序列中的数据没有全部放到tmp中
   while (begin1 <= end1)
   {
       tmp[index++] = arr[begin1++];
   }
   while (begin2 <= end2)
   {
       tmp[index++] = arr[begin2++];
   }
   //将tmp中数据挪回到arr中
   for (int i = left; i <= right; i++)
   {
       arr[i] = tmp[i];
   }
}
//归并排序
void MergeSort(int* a, int n)
{
   int* tmp = (int*)malloc(sizeof(int) * n);
   _MergeSort(a, 0, n - 1, tmp);
   free(tmp);
}
//非比较排序
void CountSort(int* arr,int n){
int max=0,min=0;
for(int i=0;i<n;i++){
if(max<arr[i]){
max=arr[i];
}
if(min>arr[i]){
min=arr[i];
}
}
int range=max-min+1;
int* count=(int*)calloc(range,sizeof(int));
for(int i=0;i<n;i++){
count[arr[i]-min]++;
}
int index=0;
for(int i=0;i<range;i++){
while(count[i]--){
arr[index++]=i+min;
}
}
}
void printf1(int* arr,int n){
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
}
void TestOP()
{
   srand(time(0));
   const int N = 100000;
   int* a1 = (int*)malloc(sizeof(int) * N);
   int* a2 = (int*)malloc(sizeof(int) * N);
   int* a3 = (int*)malloc(sizeof(int) * N);
   int* a4 = (int*)malloc(sizeof(int) * N);
   int* a5 = (int*)malloc(sizeof(int) * N);
   int* a6 = (int*)malloc(sizeof(int) * N);
   int* a7 = (int*)malloc(sizeof(int) * N);
int* a8 = (int*)malloc(sizeof(int)* N);
int* a9 =(int*)malloc(sizeof(int)*N);
int* a10=(int*)malloc(sizeof(int)*N);
   for (int i = 0; i < N; ++i)
   {
       a1[i] = rand();
       a2[i] = a1[i];
       a3[i] = a1[i];
       a4[i] = a1[i];
       a5[i] = a1[i];
       a6[i] = a1[i];
       a7[i] = a1[i];
       a8[i] = a1[i];
       a9[i]=a1[i];
   }
   int begin1 = clock();
   InsertSort(a1, N);
   int end1 = clock();

int main(){
/*int arr[6];
for(int i=0;i<6;i++){
scanf("%d",&arr[i]);
}
int n=sizeof(arr)/sizeof(arr[0]);
CountSort(arr,n);*/
//InsertSort(arr,n);
//HeapSort(arr,n);
//ShellSort(arr,n);
//BubbleSort(arr,n);
//SeclectSort(arr,n);
//QuickSort2(arr,0,n-1);
//MergeSort(arr,n);*/
//printf1(arr,n);
TestOP();
}