选择排序基本思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完直接选择排序的特性总结直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定voidSwap(int*p1,int*p2){inttmp*p1;*p1*p2;*p2tmp;}//选择排序voidSelectSort(int*a,intn){intbegin0,endn-1;while(beginend){intminibegin,maxibegin;for(intibegin1;iend;i){if(a[i]a[maxi]){maxii;}if(a[i]a[mini]){minii;}}Swap(a[begin],a[mini]);if(beginmaxi)maximini;Swap(a[end],a[maxi]);begin;--end;}}快速排序基本思想:快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止.快速排序的特性总结快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)空间复杂度O(logN)稳定性不稳定voidquickSort(int*a,intleft,intright){if(leftright)return;intkeyarr[left];// 以left为基准值intileft,jright;while(ij){// 从右往左找比key小的while(ijarr[j]pivot){j--;}if(ij){arr[i]arr[j];}// 从左往右找比pivot大的while(ijarr[i]key){i;}if(ij){arr[j--]arr[i];}}arr[i]key;quickSort(arr,left,i-1);quickSort(arr,i1,right);}上述是快速排序的基础代码voidSwap(int*p1,int*p2){inttmp*p1;*p1*p2;*p2tmp;}voidInsertSort(int*a,intn){for(inti0;in-1;i){intendi;inttmpa[end1];while(end0){if(tmpa[end]){a[end1]a[end];--end;}else{break;}}a[end1]tmp;}}intGetMidi(int*a,intleft,intright){intmidi(leftright)/2;if(a[left]a[midi]){if(a[midi]a[right]){returnmidi;}elseif(a[left]a[right]){returnright;}else{returnleft;}}else{if(a[midi]a[right]){returnmidi;}elseif(a[left]a[right]){returnleft;}else{returnright;}}}voidQuickSort(int*a,intleft,intright){if(leftright)return;// 小区间优化不再递归分割排序减少递归的次数if((right-left1)10){InsertSort(aleft,right-left1);}else{// 三数取中intmidiGetMidi(a,left,right);Swap(a[left],a[midi]);intkeyileft;intbeginleft,endright;while(beginend){// 右边找小while(beginenda[end]a[keyi]){--end;}// 左边找大while(beginenda[begin]a[keyi]){begin;}Swap(a[begin],a[end]);}Swap(a[keyi],a[begin]);keyibegin;// [left, keyi-1] keyi [keyi1, right]QuickSort(a,left,keyi-1);QuickSort(a,keyi1,right);}}上述的代码是进行优化过的快速排序,相比基础的快排,加入了取中GetMidi函数来降低基准值是极值的最坏可能,并在数量少于一定数量时将快排转为插入排序来提高算法的效率由于基础的快排较为抽象下面用一个视频进一步促进理解屏幕录制 2026-03-10 104900