如何自己做网站推广,类似凡科建站的网站,大众的网站建设,深圳网建公司前言 所谓排序#xff0c;就是将一组数据按照递增或者递减的方式进行排列#xff0c;让这组数据变得有序起来。排序在生活中运用的是十分广泛的#xff0c;各行各业都用到了排序#xff0c;比如我们在网购的时候就是按照某种排序的方式来选择东西的。所以去了解排序的实现也…前言 所谓排序就是将一组数据按照递增或者递减的方式进行排列让这组数据变得有序起来。排序在生活中运用的是十分广泛的各行各业都用到了排序比如我们在网购的时候就是按照某种排序的方式来选择东西的。所以去了解排序的实现也就是很重要的了。
目录
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[i1] --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--;}
} 它的时间复杂度是On*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,igap-1] 和区间[igap,i2*gap -1]进行插入排序依次类推//直到gap不小于数组的长度就结束int gap 1;while (gap n){//单趟归并排序for (int i 0; i n;i){//采用闭区间//[i,igap-1] 和[igap,i2*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.时间复杂度Omax(N ,范围) 3.空间复杂度O(范围) 4.排序算法的复杂度及稳定性的分析 什么是稳定性呢通俗的来说就是相同元素在进过排序后它们在数组中的相对位置不变那么稳定或者不稳定有什么影响呢在一些特殊的场景下是有影响的比如在一场考试中要给前三名颁奖如何确定前三名呢比如前五名的成绩分别是99 98 97 97 97这些的情况下是无法直接确定前三名的因为第三四五名的成绩是相同的那么这时候还有另一条规定就是这场比赛中成绩相同时用时短 的在前面。那么这样的话通过稳定的排序就可以确定前三名且对大家都是公平的但是如果是不稳定的排序这个结果是不公平的。 选择排序是不稳定的如果在一组序列中出现多个相同的最大值选择哪一个就是问题或者是下图这种情况 堆排序也是不稳定的在建堆或者选数的时候要进行向下调整向下调整的时候可能会改变相同元素的相对顺序如图 快速排序也是不稳定的因为在选某个基准进比较时可能相对顺序就会发生改变。 希尔排序也是不稳定的因为在预排序时相同的数可能被分到不同的组所以它们的相对次序就没有办法保证了。计数排序因为是统计原来数组中每个元素出现的次数所以相同元素的相对位置是没有办法保证的。
