当前位置：首页 > news >正文

排序算法详解1

news 2026/5/13 1:29:37

排序算法详解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(vector<int>&table){for(inti=1;i<table.size();++i){if(table[i]<table[i-1]){// 用j的辅助索引来找到待插入元素该放的位置上intj=i-1;inttemp=table[i];// 备份// 从[0, i - 1]while(j>=0&&table[j]>temp){table[j+1]=table[j];// 当前已经备份到后一个了j--;}table[j+1]=temp;}}}// 希尔排序（作了解）voidshellSort(vector<int>&table){for(intgap=table.size()/2;gap>0;gap/=2){for(inti=gap;i<table.size();++i){Element temp=table[i];intj;for(intj=i;j>=gap&&table[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(vector<int>&table){for(inti=0;i<table.size()-1;++i){for(intj=0;j<table.size()-1-i;++j){if(table[j]>table[j-1]){swap(table[j+1],table[j]);}}}}// 优化版本2// 引入是否交换的标志，当发现某一轮不需要交换，那么就说明已经有序，退出循环voidbubbleSortV2(vector<int>&table){for(inti=0;i<table.size()-1;++i){intisSorted=1;for(intj=0;j<table.size()-1-i;++j){if(table[j]>table[j-1]){swap(table[j+1],table[j]);isSorted=0;}}if(isSorted)break;}}// 优化版本3// 引入newIndex标记交换的索引位置，下次冒泡的时候结束位置就是newIndexvoidbubbleSortV3(vector<int>&table){intnewIndex;intn=table.size();do{newIndex=0;for(inti=0;i<n-1;++i){if(table[i]>table[i+1]){swap(table[i+1],table[i]);newIndex=i+1;}}n=newIndex;}while(newIndex>0);}

快速排序

核心：找犄点pos（返回索引值），pos小的位置上存储的都是比pos位置上的值小

找犄点的方法（含代码）

双边循环法（双指针）

// 解题版voidquickSort(intarr[],intlow,inthigh){if(low<high){inti=low,j=high;intpivot=arr[low];// 基准元素// 这样low位置就成了一个坑，可以往里面放元素while(i<j){while(i<j&&arr[j]>pivot)j--;if(i<j)arr[i++]=arr[j];// 把j位置的元素放到i位置，i++变成1while(i<j&&arr[i]<=pivot)i++;if(i<j)arr[j--]=arr[i];}arr[i]=pivot;quickSort(arr,low,i-1);// 递归排序左子数组quickSort(arr,i+1,high);// 递归排序右子数组}}// 工程版staticintpartitionDouble(vector<int>&table,intstartIndex,intendIndex){intpivot=startIndex;intleft=startIndex;intright=endIndex;// 随机将startIndex和后续的一个随机索引指向的元素进行交换while(left!=right){while(left<right&&table[right]>table[pivot])right--;while(left<right&&tablr[left]<=table[pivot])left++;if(left<right)swap(table[right],table[left]);}swap(table[pivot],table[left]);returnleft;// 此时，左边和右边相等}// 用递归思想实现[start, end]区间的排序staticvoidquickSort1(vector<int>&table,intstartIndex,intendIndex){if(startIndex>=endIndex)return;// 找到犄点intpivot=partitionDouble(table,startIndex,intendIndex);quickSort1(table,startIndex,pivot-1);quickSort1(table,pivot+1,endIndex);}voidquickSortV1(vector<int>&table){quickSort1(table,0,table.size()-1);}

单边循环法

// 解题版voidquickSort(intarr[],intlow,inthigh){if(low>=high)return;// 递归终止条件intpivot=arr[high];// 选择最后一个元素作为基准inti=low-1;// 小于基准的区域的边界for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(arr[i],arr[j]);}}// 将基准放到正确位置swap(arr[i+1],arr[high]);intpivotIndex=i+1;// 递归排序左右子数组quickSort(arr,low,pivotIndex-1);quickSort(arr,pivotIndex+1,high);}// 工程版staticintpartitionSingle(vector<int>&table,intstartIndex,intendIndex){inttemp=table[startIndex];intmark=startIndex;for(inti=startIndex+1;i<=endIndex;i++){if(table[i]<temp){mark++;swapElement(table[i],table[mark]);}}swap(table[startIndex],table[mark]);returnmark;}staticvoidquickSort2(vector<int>&table,intstartIndex,intendIndex){if(startIndex>=endIndex)return;// 找到犄点intpivot=partitionDouble(table,startIndex,intendIndex);quickSort2(table,startIndex,pivot-1);quickSort2(table,pivot+1,endIndex);}voidquickSortV2(vector<int>&table){quickSort2(table,0,table.size()-1);}