上述情况则为下面的代码

简单来说,希尔排序的工作原理是:

1. 按照一个增量 gap,将记录分组。
   

   

   intGetMidIndex(int*a,intleft,intright){intmid =(left +right)/2;if(a[left]<a[mid]){if(a[mid]<a[right]){returnmid;}elseif(a[left]>a[right]){returnleft;}else//(a[left] <= a[right]){returnright;}}else//(a[left] > a[mid]){if(a[mid]>a[right]){returnmid;}elseif(a[left]>a[right]){returnright;}else{returnleft;}}}// 快速排序hoare版本三数取中优化intPartSort1(int*a,intleft,intright){intkeyi =GetMidIndex(a,left,right);Swap(&a[keyi],&a[left]);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[left],&a[keyi]);returnright;}

   3.2.2.5 非递归版本

   快速排序的非递归版本需要使用栈，而C语言的库中并没有关于栈的数据结构，那么这里需要自己实现栈。

   4.2.1 归并排序的递归版本实现

   #include<stdio.h>#include<stdlib.h>#include<string.h>#include<stdbool.h>// 归并排序递归实现void_MergeSort(int*a,intleft,intright,int*tmp){intmid =(left +right)/2;//[left , mid] [mid + 1 , right]if(mid >left)_MergeSort(a,left,mid,tmp);if(right >mid +1)_MergeSort(a,mid +1,right,tmp);inti =left;intbegin1 =left,end1 =mid;intbegin2 =mid +1,end2 =right;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 +left,tmp +left,sizeof(int)*(right -left +1));}voidMergeSort(int*a,intn){int*tmp =(int*)malloc(sizeof(int)*n);_MergeSort(a,0,n -1,tmp);free(tmp);}

   4.2.2 归并排序的非递归版本实现

   #include<stdio.h>#include<stdlib.h>#include<string.h>//归并排序非递归实现voidMergeSortNonR(int*a,intn){int*tmp =(int*)malloc(sizeof(int)*n);if(tmp ==NULL){perror("malloc");return;}intgap =1;while(gap <n){intj =0;for(inti =0;i <n;i +=2*gap){intbegin1 =i,end1 =i +gap -1;intbegin2 =i +gap,end2 =i +2*gap -1;//三种越界情况//end1 begin2 end3 都越界//begin2 end3 越界//end3 越界if(end1 >=n ||begin2 >=n){break;}if(end2 >=n){end2 =n -1;}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));}gap *=2;}free(tmp);}

   4.3 归并排序的总结：

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

      我个人理解为是：将待排序的数据依次与前面有序的数组比较，直到形成一个新的有序数组。我们实现后可以进行性能测试的对比。

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

      2.1.2 直接选择排序过程及代码实现

      
      上面的动态图显示的是一次选择一个最小/最大的值进行交换，下面我写的的代码是直接选择排序的优化版本，一次挑出最大和最小的分别与最右边与最左边进行交换。

      intPartSort2(int*a,intleft,intright){intkeyi =left;intkey =a[left];while(left <right){while(left <right &&a[right]>=key){right--;}a[left]=a[right];while(left <right &&a[left]<=key){left++;}a[right]=a[left];}a[right]=key;returnleft;}voidQuickSort(int*a,intleft,intright){intkeyi =PartSort2(a,left,right);//[left , keyi - 1] [keyi] [keyi + 1 , right]if(keyi -1>left){QuickSort(a,left,keyi -1);}if(right >keyi +1){QuickSort(a,keyi +1,right);}}

      3.2.2.3 前后指针法

      
      前后指针法的思想是选取待排序数组的左边作为关键字，使用一个变量keyi记录关键字的下标，再使用两个下标分别记录关键字的下标（prev）和关键字左边的一个元素（cur）,先使cur从左向右遍历，若cur指向的元素比关键字大，那么cur向后继续遍历。所有距离为 gap的倍数的记录放在同一组。当gap == 1时，数组已经接近有序的了，这样就
      会很快。排序的概念

   3. • 1. 排序的使用：
      • 2. 稳定性：
      • 3. 内部排序：
      • 4. 外部排序︰
      • 5. 排序的用途：
   4. 二、栈为空时，说明所有区间都排序结束，则快速排序完成。

      ---

      1.1.2 直接插入排序的思想及个人理解

      直接插入排序的思想：当插入第i(i>=1)个元素时，前面的array[0],array[1]…array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2]…的排序码顺序进行比较，找到插入位置即将array[i]插入.原来位置上的元素顺序后移。排序算法复杂度及稳定性分析

      

      

      结尾

      如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。

      下面实现了三数取中的代码，并且在hoare版本中的使用，三数取中在上面三个方法使用的方法相同，在下面非递归版本中也会使用到。排序的概念

      1. 排序的使用：

      所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

      记录交换后关键字的下标，将关键字左边和右边分割成为两个待排序区间，重复上面第一次排序的操作继续将剩下的待排序区间进行排序，直到区间不存在或者是区间内只有一个元素，那么当前区间不可继续分割，则这次排序才算结束。

      QuickSortNonR.c 文件的实现

      #include<stdio.h>#include"Stack.h"// 快速排序 非递归实现voidQuickSortNonR(int*a,intleft,intright){Stack st;StackInit(&st);intend =right;intbegin =left;StackPush(&st,end);StackPush(&st,begin);while(!StackEmpty(&st)){begin =StackTop(&st);StackPop(&st);end =StackTop(&st);StackPop(&st);intkeyi =PartSort1(a,begin,end);//[begin , keyi - 1] [keyi] [keyi + 1 , end]if(end >keyi +1){StackPush(&st,end);StackPush(&st,keyi +1);}if(keyi -1>begin){StackPush(&st,keyi -1);StackPush(&st,begin);}}}

      stack.h 文件的实现

      #include<stdio.h>#include<stdlib.h>#include<assert.h>// 支持动态增长的栈typedefintSTDataType;typedefstructStack{STDataType*a;inttop;// 栈顶intcapacity;// 容量 }Stack;// 初始化栈 voidStackInit(Stack*ps);// 入栈 voidStackPush(Stack*ps,STDataType data);// 出栈 voidStackPop(Stack*ps);// 获取栈顶元素 STDataType StackTop(Stack*ps);// 获取栈中有效元素个数 intStackSize(Stack*ps);// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack*ps);// 销毁栈 voidStackDestroy(Stack*ps);

      stack.c 文件的实现

      #include"Stack.h"// 初始化栈 voidStackInit(Stack*ps){assert(ps);ps->capacity =0;ps->top =0;//top指向栈顶的后面一个元素ps->a =NULL;}voidStackFull(Stack*ps){assert(ps);intnewcapacity =ps->capacity ==0?4:ps->capacity *2;STDataType*tmp =(STDataType*)realloc(ps->a,sizeof(STDataType)*newcapacity);if(tmp ==NULL){perror("realloc");return;}ps->a =tmp;ps->capacity =newcapacity;}// 入栈 voidStackPush(Stack*ps,STDataType data){assert(ps);if(ps->capacity ==ps->top)StackFull(ps);ps->a[ps->top]=data;ps->top++;}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack*ps){assert(ps);returnps->top ==0;}// 出栈 voidStackPop(Stack*ps){assert(ps);assert(!StackEmpty(ps));//栈为空，则不能继续出栈ps->top--;}// 获取栈顶元素 STDataType StackTop(Stack*ps){assert(ps);assert(!StackEmpty(ps));//栈为空，则无栈顶元素returnps->a[ps->top -1];}// 获取栈中有效元素个数 intStackSize(Stack*ps){assert(ps);returnps->top;//由于top是指向栈顶元素的下一个位置		//而元素个数正好是下标 + 1 ，也就是top}// 销毁栈 voidStackDestroy(Stack*ps){assert(ps);free(ps->a);ps->a =NULL;ps->capacity =0;ps->top =0;}

      3.2.3 快速排序的时间复杂度

      快速排序的时间复杂度如果每次都平分两个待排序数组时为O(n*logn --> n * 以二为底n的对数)，而在最坏的情况下时间复杂度为O(n^2),但是在三数取中的优化下，快速排序不会变为最坏的情况,一般时间复杂度为O(n*logn)。

      ---

      1.1.3 直接插入排序的排序过程及代码实现

      a. 静态排序过程
      
      b. 动态排序过程

      
      c. 代码实现

      #include<stdio.h>voidInsertSort(int*arr ,intn){for(inti =0;i <n -1;i++){intend =i;inttmp =arr[end +1];//tmp 记录需要插入的值while(end >=0){if(arr[end]>tmp)//如果arr[end] > tmp 则 arr[end] 向后移动一位{arr[end +1]=arr[end];end--;}else//如果arr[end] <= tmp ,则将tmp放到 arr[end] 的后面{break;}}//如果需要插入的数是最小的时候，是特殊情况需要放在第一位arr[end +1]=tmp;}}

      注意：
      这里有一个很巧妙的设计，上述代码只分了两种情况，而一般情况下的想法是将比较分为三种情况：
      ⑴待排序数从后往前与有序数列比较时较小，被比较数向后移动，待排序数向前继续比较
      ⑵待排序数从后往前与有序数列比较时较大或者相等时，待排序数放在比较数后面
      ⑶待排序数比有序数列中的任何一个数据都要小时，无法继续比较(待排序数已经到了数组首元素位置，继续比较的数无意义且已经越界)，放在有序数列的第一个位置上

      而这里则将( 2 )( 3 )两种情况合并为一种，详细来说就是，( 2 )( 3 )两种情况都是需要赋值的，而按照第一种情况的相反方向列为赋值情况，那么待排序数就到了正确的位置，赋值并跳出循环，但循环有两种停止情况，①不满足循环条件（待排序是比有序数组中的每一位都小） ②待排序数放在正确的位置，而我们并不能确定是上面两种情况的哪一种，所以要判断待排序数是否是不满足循环条件，将其赋值到有序数组的首元素位置。

   5. 当gap > 1时都是预排序，目的是让数组更接近于有序。

      intPartSort3(int*a,intleft,intright){intprev =left;intcur =left +1;intkeyi =left;while(cur <=right){if(a[cur]<a[keyi]&&cur !=prev){prev++;Swap(&a[prev],&a[cur]);}cur++;}Swap(&a[keyi],&a[prev]);returnprev;}voidQuickSort(int*a,intleft,intright){intkeyi =PartSort3(a,left,right);//[left , keyi - 1] [keyi] [keyi + 1 , right]if(keyi -1>left){QuickSort(a,left,keyi -1);}if(right >keyi +1){QuickSort(a,keyi +1,right);}}

      3.2.2.4 快速排序的优化（三数取中）

      前面未优化的快速排序有一个致命缺点，就是当待排序数组有序或接近有序时，选取关键字并排序后需要将待排序数组分割为两个区间，而有序或接近有序的数字分割时，并不能实现相对的平分，使得一个区间占据了一两个元素，而另外一个区间占据相对很多的数据，导致每一次排序几乎都是O(n的递减)，最终快速排序的时间复杂度变为O(n^2)。

      三数取中的实现是取区间最左边、

      递归版本在向下传递参数时，每一层都有单独的两个变量存储待排序区间的范围，而快速排序非递归版本没有这个能力，那么非递归版本需要通过栈来存储待排序数组的左右两边的下标，将待排序数组排序后，记录关键字的下班，将待排序数组分割为两个区间，并将两个区间范围的下标入栈，形成两个新的待排序数组，重复上面的操作，取出待排序数组的范围进行下一次排序，直到栈不为空。当所有的区待排序区间都不存在或是只有一个元素时，那么所有的元素就到了它应该在的位置，则排序完成。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
      

      3.2.4 快速排序的总结

      1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
      2. 时间复杂度：O(n*logn)
      3. 空间复杂度：O(logn)
      4. 稳定性：不稳定

      ---

      4. 归并排序

      4.1 归并排序的基本思想：

      归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。排序的原理及实现

      1. 插入排序

      1.1 直接插入排序

      1.1.1 直接插入排序在现实中的应用

      
      相信大家都玩过牌，在摸牌阶段，每摸一张牌都从后往前依次比较，若摸起来的这张牌比比较的这张牌小，则继续向前比较，直到遇到比它小的那张牌，则将摸起来的那张牌放在它的后面，若没有比摸起来的这张牌小的，则将这张牌放在最前面。排序算法复杂度及稳定性分析

   6. 结尾