排序算法详解1

排序算法详解1一、前言最近一直忙着刷题今天继续来更新啦~今天是排序算法二、排序算法2.1 概述我们拿到一个数据结构就会就其中进行一定的操作比如让数据的关键字有序存放这里的序找数据的唯一标识key按照排序默认是从小到大2.2 特性内排序、外排序内指内存。程序是可以直接寻址的。数据量很大时内存存不下就需要借助外存。排序最终影响的是外存存储的数据。目前阶段主要是内存排序就地排序、非就地排序voidfun(int*data,intnum);// 就地排序int*fun(constint*data,intnum);// 非就地排序稳定排序、非稳定排序当存在数值相等时往往本在前面的还是在前面就是相对稳定一些更具有规律2.3 算法评价指标时间复杂度空间复杂度测试框架准备数据随机生成- 执行排序 - 验证结果 - 输出执行时间2.4 排序算法2.4.1 插入排序概述将数据按照一定的顺序一个一个插入到有有序的表中最终得到已经排好序的数据类似玩扑克中的摸牌插入数组将数组分为两个部分已排序区和未排序区方法直接插入排序折半插入排序希尔排序缩小增量排序先迈大步子然后不断缩小步长增量n / 2, n / 4…代码// 1. 默认第一个元素就是有序那么从第二个元素开始和前面的有序区的值进行比较// 2. 待插入的元素i和已经有序的区域从后往前依次查找voidinsertSort(vectorinttable){for(inti1;itable.size();i){if(table[i]table[i-1]){// 用j的辅助索引来找到待插入元素该放的位置上intji-1;inttemptable[i];// 备份// 从[0, i - 1]while(j0table[j]temp){table[j1]table[j];// 当前已经备份到后一个了j--;}table[j1]temp;}}}// 希尔排序作了解voidshellSort(vectorinttable){for(intgaptable.size()/2;gap0;gap/2){for(intigap;itable.size();i){Element temptable[i];intj;for(intji;jgaptable[j-gap]temp;j-gap){table[j]table[j-gap];}table[j]temp;}}}时间复杂度O(n2n^2n2)2.4.2 交换排序方法冒泡排序// 优化版本1// 第一次遍历[0, n - 1), 第二次遍历[0, n - 2)...遍历n - 1次voidbubbleSortV1(vectorinttable){for(inti0;itable.size()-1;i){for(intj0;jtable.size()-1-i;j){if(table[j]table[j-1]){swap(table[j1],table[j]);}}}}// 优化版本2// 引入是否交换的标志当发现某一轮不需要交换那么就说明已经有序退出循环voidbubbleSortV2(vectorinttable){for(inti0;itable.size()-1;i){intisSorted1;for(intj0;jtable.size()-1-i;j){if(table[j]table[j-1]){swap(table[j1],table[j]);isSorted0;}}if(isSorted)break;}}// 优化版本3// 引入newIndex标记交换的索引位置下次冒泡的时候结束位置就是newIndexvoidbubbleSortV3(vectorinttable){intnewIndex;intntable.size();do{newIndex0;for(inti0;in-1;i){if(table[i]table[i1]){swap(table[i1],table[i]);newIndexi1;}}nnewIndex;}while(newIndex0);}快速排序核心找犄点pos返回索引值pos小的位置上存储的都是比pos位置上的值小找犄点的方法含代码双边循环法双指针// 解题版voidquickSort(intarr[],intlow,inthigh){if(lowhigh){intilow,jhigh;intpivotarr[low];// 基准元素// 这样low位置就成了一个坑可以往里面放元素while(ij){while(ijarr[j]pivot)j--;if(ij)arr[i]arr[j];// 把j位置的元素放到i位置i变成1while(ijarr[i]pivot)i;if(ij)arr[j--]arr[i];}arr[i]pivot;quickSort(arr,low,i-1);// 递归排序左子数组quickSort(arr,i1,high);// 递归排序右子数组}}// 工程版staticintpartitionDouble(vectorinttable,intstartIndex,intendIndex){intpivotstartIndex;intleftstartIndex;intrightendIndex;// 随机将startIndex和后续的一个随机索引指向的元素进行交换while(left!right){while(leftrighttable[right]table[pivot])right--;while(leftrighttablr[left]table[pivot])left;if(leftright)swap(table[right],table[left]);}swap(table[pivot],table[left]);returnleft;// 此时左边和右边相等}// 用递归思想实现[start, end]区间的排序staticvoidquickSort1(vectorinttable,intstartIndex,intendIndex){if(startIndexendIndex)return;// 找到犄点intpivotpartitionDouble(table,startIndex,intendIndex);quickSort1(table,startIndex,pivot-1);quickSort1(table,pivot1,endIndex);}voidquickSortV1(vectorinttable){quickSort1(table,0,table.size()-1);}单边循环法// 解题版voidquickSort(intarr[],intlow,inthigh){if(lowhigh)return;// 递归终止条件intpivotarr[high];// 选择最后一个元素作为基准intilow-1;// 小于基准的区域的边界for(intjlow;jhigh;j){if(arr[j]pivot){i;swap(arr[i],arr[j]);}}// 将基准放到正确位置swap(arr[i1],arr[high]);intpivotIndexi1;// 递归排序左右子数组quickSort(arr,low,pivotIndex-1);quickSort(arr,pivotIndex1,high);}// 工程版staticintpartitionSingle(vectorinttable,intstartIndex,intendIndex){inttemptable[startIndex];intmarkstartIndex;for(intistartIndex1;iendIndex;i){if(table[i]temp){mark;swapElement(table[i],table[mark]);}}swap(table[startIndex],table[mark]);returnmark;}staticvoidquickSort2(vectorinttable,intstartIndex,intendIndex){if(startIndexendIndex)return;// 找到犄点intpivotpartitionDouble(table,startIndex,intendIndex);quickSort2(table,startIndex,pivot-1);quickSort2(table,pivot1,endIndex);}voidquickSortV2(vectorinttable){quickSort2(table,0,table.size()-1);}时间复杂度O(nlogn)三、小结还有许多其他排序算法敬请期待~