插入排序，选择排序，交换排序，归并排序和非比较排序（C语言版）

前言

        所谓排序，就是将一组数据按照递增或者递减的方式进行排列，让这组数据变得有序起来。排序在生活中运用的是十分广泛的，各行各业都用到了排序，比如我们在网购的时候就是按照某种排序的方式来选择东西的。所以去了解排序的实现也就是很重要的了。

目录

1.排序的概念

2.常见的排序算法

3.常见的排序算法的实现

        3.1插入排序

                3.1.1直接插入排序 

                3.1.2希尔排序 

        3.2选择排序

                3.2.1堆排序

                3.2.2直接选择排序  

        3.3交换排序

                3.3.1冒泡排序

                3.3.2快速排序 

        3.4归并排序

                3.4.1归并排序 

                3.4.2归并排序应用-外排序

        3.5非比较排序 

4.排序算法的复杂度及稳定性的分析  

---

1.排序的概念

        排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小按照一定的规律变成递增或者递减的序列。

        稳定性： 假定待排序的记录序列中，存在多个具有相同关键字的记录，经过排序后这些记录的相对次序没有发生变化，即在原序列中r[i] = r[j],且r[i]在r[j]之前，而在排序后r[i]任在r[j]之前，则称这种排序算法是稳定的，否则就是不稳定的。

        内排序：数据元素全部放在内存中的排序。

        外排序：数据元素太多不能同时放在内存中，根据排序过程中的要求能在内外存之间移动数据的排序。

2.常见的排序算法

         

3.常见的排序算法的实现

        3.1插入排序

        基本思想：把待排序的记录按其关键码值逐个插入到一个已经排好序的有序序列中，直到所有的序列插完为止，得到一个新的有序序列。

        实际上我们在玩扑克排的时候，就用到了插入排序的思想。

         

                3.1.1直接插入排序 

        当插入第i个元素的时候前面的array[0],array[1],…,array[i-1]已经排好序，此时用arryy[i]的排序码与array[i -1],array[i-2],array[i-3],...的排序码顺序比较找到插入的位置即将array[i]插入，原来位置上的元素顺序后移。

        比较过程，如果是排升序，先与当前值比较，如果比当前值小就和当前值的前一个元素比较，如果比当前值的前一个元素大，就插入到当前值的前一个元素的后面，如果比当前值的前一个元素小，继续去前面进行比较，知道找到合适的位置进行插入，如果是最小的，那么就要插入到数组的开头。如图：

void InsertSort(int* a, int n)//升序排序
{assert(a);for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[end + 1];//保存数据，后面移动的时候数据会被覆盖while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];//将数据向后移动空出位置--end;//迭代继续向前比较}else{break;//插入到}}a[end + 1] = tmp;}
}

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

        1.时间复杂度为O(N*2)。

        2.排序的序列越接近有序，时间复杂度越低。

        3.稳定性：稳定。

        4.空间复杂度O(1)，它是一种稳定的排序。

        实现代码：

                3.1.2希尔排序 

        希尔排序又称缩小增量排序法。希尔排序的基本思想是：先选定一个整数，把待排序的文件中所记录分成一个个组，所有距离为gap的记录在一个组内，并对每一组内的记录进行排序。然后，重复上述分组和排序的工作。当gap = 1时，所以记录统一排好序。

        说白了，希尔排序从直接插入排序找突破口，虽然直接插入排的时间复杂度很高，但是直接插入排序在有序或者接近有序的情况下，效率会是很好的，那么怎么样让它接近有序呢？这就要采用预排序了。通过预排序让数组接近有序，最后一次在进行直接插入排序，就会很快，通过这样的方式 希尔排序对直接插入排序进行了很好的优化。

        希尔排序分为两步：

        1.对数组进行预排序

        将数组按照间隔gap分为很多组，先对间隔为gap的组进行排序，使得间隔为gap的是有序的，然后缩小间隔gap。在重复上述过程。 

        2.直接插入排序

        当gap等于1时，就相当于是直接插入排序啦，听起来是不是很简单啊，hhhh。

 

        如图：

        

//希尔排序
void ShellSort(int* a, int n)
{assert(a);//确保指针不为空int gap = n;while (gap > 1){gap = gap / 3 + 1;//保证最后一次排序的间隔是1，进过计算gap按照三分之一减少是最优的for (int i = 0; i < n - gap; ++i)//排升序{int end = i;int tmp = a[end + gap];//防止数据被覆盖while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];//移动数组，继续在前面比较end = end - gap;}else{break;}}a[end + gap] = tmp;//将数据插入到数组中}Print(a, 10);printf("  gap = %d\n", gap);printf("\n");}}

        希尔排序的特性总结

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

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

        3.希尔排序的时间复杂度不好计算，因为gap的取值有很多方法，导致很难去计算，因此在很多书里面希尔排序的时间复杂度都不固定。

 

        因为这里的gap是按照Knuth的方法取值的，所以暂时按照来计算。

         

        3.2选择排序

        基本思想：每次从待排序的数据中选出最小（或者最大的元素），存放到序列的起始位置，直到待排序的数组排序完为止。 

                3.2.1堆排序

        详见：堆排序 

                3.2.2直接选择排序  

         排升序：在元素集合array[i]-array[n-1],选择关键码子最大（最小）的数据元素。

        若它不是这组元素中的最后一个 （第一个）元素，则将它与这组元素中的最后一个（第一个）元素交换。

        在剩余的array[i]--array[n -2](array[i+1] --array[n-1])集合中重复上述步骤，直到集合剩下一个元素。

void SelectSort(int* a, int n)
{assert(a);//确保a存在//排升序int left = 0;int right = n - 1;while (left < right){int maxDex = right;int minDex = left;//遍历剩余的数组每次找出最大的和最小的将最大的换到n-1的位置，将最小的放到j位置for (int i = left; i <= right; ++i){if (a[maxDex] < a[i] ){maxDex = i;//记录最大值的下标}if (a[minDex] > a[i]  ){minDex = i;//记录最小值的下标}}Swap(&a[minDex], &a[left]);if (left == maxDex)//说明最大值的下标在最左边，上一步的交换让最大值已经不是最左边，而是下标minDexmaxDex = minDex;Swap(&a[maxDex], &a[right]);left++;right--;}
}

         它的时间复杂度是O（n*n）。

void SelectSort(int* a, int n)
{assert(a);//确保a存在//排升序int left = 0;int right = n - 1;while (left < right){int maxDex = right;int minDex = left;//遍历剩余的数组每次找出最大的和最小的将最大的换到n-1的位置，将最小的放到j位置for (int i = left; i <= right; ++i){if (a[maxDex] < a[i] ){maxDex = i;//记录最大值的下标}if (a[minDex] > a[i]  ){minDex = i;//记录最小值的下标}}Swap(&a[minDex], &a[left]);if (left == maxDex)//说明最大值的下标在最左边，上一步的交换让最大值已经不是最左边，而是下标minDexmaxDex = minDex;Swap(&a[maxDex], &a[right]);left++;right--;}
}

        3.3交换排序

                3.3.1冒泡排序

        详见 冒泡排序

                3.3.2快速排序 

        详见快速排序 

        快速排序除了递归的实现方法外，还有非递归的实现方法，那么，如何通过非递归来实现快排的呢？ 让我们一起来试试吧，我们都知道递归的方法实现快排是通过函数调用栈帧来实现的，其实非递归也是通过模拟函数调用栈帧的过程，通过数据结构的栈来模拟实现的。

        虽然数据结构的栈和操作系统的栈不是一会事情，但是它们的性质是相同的（后进先出），如何通过栈来模拟实现呢？

        代码： 

// 快速排序 非递归实现
void QuickSortNonR(int* a, int begin, int end)
{//创建并初始化栈Stack st;StackInit(&st);//将区间[left,right]入栈StackPush(&st, end);StackPush(&st, begin);//通过栈来模拟快排递归时的调用//数据结构实现的栈和操作系统的栈的特性是一样的while (!StackEmpty(&st)){int left = StackTop(&st);StackPop(&st);int right = StackTop(&st);StackPop(&st);//如栈的时候先右后左，出栈的时候先左后右int midi = PartSort1(a, left, right);//对子区间进行快速排序的单趟排序//将左右子区间都入栈if (midi + 1 < right)//右边区间至少存在一个数{StackPush(&st, right);StackPush(&st, midi + 1);}if (left < midi - 1)//左边区间至少存在一个数{StackPush(&st, midi - 1);StackPush(&st, left);}}StackDestory(&st);
}

        3.4归并排序

                3.4.1归并排序 

                 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型应用，将已经有序的子序列合并，得到完全有序的的序列；即先使每个子序列都有序，在合并子序列使得整个区间有序，若将两个有序表合并成一个有序表，称为二路归并，归并排序的核心步骤：

代码：

//单趟归并排序
void _MergeSortSignal(int *a, int begin1, int end1, int begin2, int end2, int *tmp)//闭区间
{int begin = begin1;//保存数组起始的位置方便拷贝tmp = (int*)malloc(sizeof(int) * (10 + 1));int i = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//将剩下的一个数组尾插到tmpwhile (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}for (int j = begin ; j <= end2; ++j){a[j] = tmp[j];}free(tmp);}
// 归并排序递归实现
void _MergeSort(int* a, int left, int right, int * tmp)
{if (left >= right)//区间只剩下一个数{return;}int midi = (left + right) / 2;_MergeSort(a, left, midi, tmp);_MergeSort(a, midi + 1, right, tmp);//合并有序的小区间_MergeSortSignal(a, left, midi, midi + 1, right, tmp);}
void MergeSort(int* a, int n)
{//int* tmp = (int*)malloc( sizeof(int) * n);_MergeSort(a, 0, n - 1,NULL);//闭区间[left,right]//free(tmp);
}

 

        归并排序的非递归法： 

        如果采用栈来模拟会将问题变得复杂，通过上面的图，我们不难发现归并排序是将要排序的区间不断缩小的过程直到要排序的区间变得有序，那么怎么样是一定有序的呢，我们不难发现，如果区间只有一个数的时候一定是有序的，所以我们采取这个思路，刚开始让相邻的连个数进行归并，此时间隔gap为一，下一次，相邻的两个数已经有序了，那么此时要将区间长度为2的相邻的两个子区间归并为一个有序的区间，此时gap = 2，依次类推增大gap就行了，什么时候结束呢，直到gap大于等于数组的长度时，数组肯定是有序的。这时候在进行归并已经没有意义了。

        注意：划分子区间进行合并的时候，有可能第二个区间的长度小于第一个区间的长度，或者第二个区间不存在，因此需要注意，对第二个区间的边界进行修正或者只有第一个子区间时，这次就不需要归并排序了。

//将两个有序小区间合并为一个
void _MergeSortSignal(int *a, int begin1, int end1, int begin2, int end2, int *tmp)//闭区间
{int begin = begin1;//保存数组起始的位置方便拷贝tmp = (int*)malloc(sizeof(int) * (10 + 1));int i = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//将剩下的一个数组尾插到tmpwhile (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}for (int j = begin ; j <= end2; ++j){a[j] = tmp[j];}free(tmp);}
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{//实现思路：这里如果借助栈来模拟会将问题变得复杂起来，所以可以采取循环的方式//直接归并，第一次是相邻的两个数归并，这时候gap为1，第二次gap为而就是区间[i,i+gap-1] 和区间[i+gap,i+2*gap -1]进行插入排序，依次类推//直到gap不小于数组的长度就结束int gap = 1;while (gap < n){//单趟归并排序for (int i = 0; i < n;++i){//采用闭区间//[i,i+gap-1] 和[i+gap,i+2*gap]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//调用将两个数组合并成一个数组的函数if (begin2 >= n){break;//说明要排序第二组不存在，只有第一组,本次不需要再排}if (end2 >= n){//需要修正第二组的边界end2 = n - 1;}_MergeSortSignal(a, begin1, end1, begin2, end2, NULL);}gap *= 2;}
}

 

                3.4.2归并排序应用-外排序

           归并排序和其他几种排序不太一样，其它几种排序适合在内存中进行排序，而归并排序不仅可以在内存中进行排序，当数据很多时，多到内存中放不下，只能存放到文件中此时其它的排序都不怎么好用，但是归并排序却可以对数据进行排序并且是在文件中进行，所以归并排序也是外排序。

        现在模拟一种场景，假设，有海量的数据，这些数据无法一次加载到内存中，现在请你编写一个程序对这些数据进行排序，并将结果保存在文件中。

        思路是：

        1.首先我们需要将这些数据划分成很多份，并且划分出来的每一份都可以一次性加载到内存中并且进行排序。

        2.将划分好的数据一次存放到子文件中，并且使用快排将这些数据变得有序。

        3.此时已经满足归并排序的先决条件，每个子序列都是有序的，此时我们只需要每次读取两个文件中的数据将它们比较并且合并到一个新的文件中，如法炮制直到最后将所有的有序子区间合并成一个文件，此时这个文件中的数据都是有序的。

        

代码：

//将两个文件中的有序数据合并到一个文件中并且保持有序
void _MergeFile(const char* file1, const char* file2, const char* mfile)
{FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){printf("fout1打开文件失败\n");exit(-1);}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){printf("fout2打开文件失败\n");exit(-1);}FILE* fin = fopen(mfile, "w");if(fin == NULL){printf("fin打开文件失败\n");exit(-1);}int num1, num2;int ret1 = fscanf(fout1, "%d\n", &num1);int ret2 = fscanf(fout2, "%d\n", &num2);//在文件中读数据进行归并排序while (ret1 != EOF && ret2 != EOF){if (num1 < num2){fprintf(fin, "%d\n", num1);//再去fout1所指的文件中读取数据ret1 = fscanf(fout1, "%d\n", &num1);}else{fprintf(fin, "%d\n", num2);//再去fout2所指的文件中读取数据ret2 = fscanf(fout2, "%d\n", &num2);}}while (ret1 != EOF){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);}while (ret2 != EOF){fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);}fclose(fout1);fclose(fout2);fclose(fin);
}
void MergeSortFile(const char* file)//文件归并排序
{//打开文件FILE* fout = fopen(file, "r");if (fout == NULL){printf("打开文件失败\n");exit(-1);}int n = 10;int a[10] = { 0 };char subr[1024] ;/*memset(subr, 0, 1024);memset(a, 0, sizeof(int) * n);*/int num = 0;int i = 0;int fileI = 1;while (fscanf(fout, "%d\n",&num )!=EOF){if (i < n - 1){a[i++] = num;} else{a[i] = num;QuickSort(a, 0, n - 1);//对内存中的数据进行排序sprintf(subr, "%d", fileI++);FILE* fin = fopen(subr, "w");if (fin == NULL){printf("打开文件失败\n");exit(-1);}//写数据到文件中for (int j = 0; j < n; ++j){fprintf(fin, "%d\n", a[j]);}//关闭文件i = 0;//置零对下一组数据进行操作/*memset(subr, 0, 1024);memset(a, 0, sizeof(int) * n);*/fclose(fin);}}//外排序//利用互相归并到文件中，实现整体有序char file1[100] = "1";char file2[100];char mfile[100] = "12";for (int i = 2; i <= n; ++i){sprintf(file2, "%d", i);//读取FIle和file2，进行归并排序出mfile_MergeFile(file1, file2, mfile);strcpy(file1,mfile);sprintf(mfile, "%s%d", mfile, i + 1);}fclose(fout);return NULL;
}

 

        3.5非比较排序 

        非比较排序顾名思义就是不用对元素进行比较就可以进行排序了，这里介绍的是计数排序， 

计数排序又叫鸽巢原理，是对哈希直接定值法的变形应用。操作步骤：

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

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

 

代码：

// 计数排序
void CountSort(int* a, int n)
{//先遍历数组，找出最大值和最小值用来确定范围int max = a[0];int min = a[0];for (int i = 0; i < n; ++i){if (max < a[i]){max = a[i];}if (min > a[i]){min = a[i];}}//然后根据最大值和最小值的范围开辟空间int range = max - min + 1;int* CountArray = (int*)calloc(sizeof(int), range);//统计原数组中每个数出现的次数for (int i = 0; i < n; ++i){CountArray[ a[i] - min ] ++ ;//利用相对位置来计算数据出现的个数}/*Print(CountArray, 9);printf("\n");*///将临时数组中的数，覆盖到原数组中int j = 0;for (int i = 0; i < range; ++i){while (CountArray[ i ]--){a[j++ ] = i + min;//将每个数据从临时数组中拿出来加上相对数据min，然后对数组进行覆盖}}//释放临时开辟的空间free(CountArray);
}

 

        计数排序的特性总结：

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

  2.时间复杂度O（max(N ,范围)）

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

   

4.排序算法的复杂度及稳定性的分析  

         

        什么是稳定性呢，通俗的来说就是相同元素在进过排序后它们在数组中的相对位置不变，那么稳定或者不稳定有什么影响呢？在一些特殊的场景下是有影响的，比如，在一场考试中，要给前三名颁奖，如何确定前三名呢？比如前五名的成绩分别是：99 98 97 97 97，这些的情况下，是无法直接确定前三名的，因为第三，四，五名的成绩是相同的，那么这时候还有另一条规定就是这场比赛中成绩相同时，用时短 的在前面。那么这样的话，通过稳定的排序就可以确定前三名且对大家都是公平的，但是如果是不稳定的排序，这个结果是不公平的。 

        选择排序是不稳定的，如果在一组序列中出现多个相同的最大值，选择哪一个就是问题，或者是下图这种情况： 

        堆排序也是不稳定的，在建堆或者选数的时候要进行向下调整，向下调整的时候可能会改变相同元素的相对顺序，如图： 

         快速排序也是不稳定的，因为在选某个基准进比较时，可能相对顺序就会发生改变。        

        希尔排序也是不稳定的，因为在预排序时，相同的数可能被分到不同的组，所以它们的相对次序就没有办法保证了。计数排序因为是统计原来数组中每个元素出现的次数，所以相同元素的相对位置是没有办法保证的。