2019獨角獸企業重金招聘Python工程師標準>>>

首先初始化了一個MAX大小的數組，用亂序函數將數組打亂，用于測試各個排序函數，先附上要測試的幾個基礎排序函數，后面附上亂序函數和主調度函數。代碼就那么幾行，只是注釋的思亂占了比較多的行數

快速排序

//快速排序，思想的重點是?遞歸+分組（分治）+前后交叉操作 void?quickSort(int?*array,?int?low,?int?hight) {//判斷是否滿足條件if?(hight?<=?low) //如果只有一個元素或者前后錯位了，就不用排序了，一個元素就是成序的return;//滿足排序條件，進入排序部分int?i?=?low,?j?=?hight; //定義函數內的臨時變量為low和hight的副本，避免修改low和?hight，后面還要使用int?temp?=?array[low];//對整個序列進行一次篩選，以目標值為分割點，只有當i<j時表示遍歷沒有完成，需要繼續遍歷while?(i?<?j){while?(i<j?&&?array[j]>temp){j--;}if?(i?<?j){array[i++]?=?array[j];}while?(i?<?j?&&?array[i]?<?temp){i++;}if?(i?<?j){array[j--]?=?array[i];}}//循環跳出，證明i=j，遍歷相遇，一輪篩選完成，將目標數放在中間array[i]?=?temp;//遞歸部分//將前半部分交給快排函數quickSort(array,?low,?i?-?1);//將后半部分交給快拍函數quickSort(array,?i?+?1,?hight); }

shell排序（基于插入排序）

//shell排序（希爾排序） void?shellSort(int?*array,?int?size,?int?d) {//循環1?控制步長的循環for?(int?increment?=?d;?increment?>?0;?increment?/=?2){//循環2?屬于插入排序內容，控制遍歷次步長可以訪問到的元素for?(int?i?=?increment;?i?<?size;?i?+=?increment){int?temp?=?array[i];int?j?=?i?-?increment;//循環3?屬于插入排序內容，賦值尋找目前元素可以插入的位置while?(j?>=?0?&&?array[j]>temp){array[j?+?increment]?=?array[j];j?-=?increment;}array[j?+?increment]?=?temp;}} }

shell排序（基于選擇排序）

相比于基于插入排序實現的shell排序，這個看起來循環多，實現的時候邏輯也不簡單于基于插入排序，

不知道是我寫的問題，還是問題的本身就是這樣的，求指教

void?shellSort2(int?*array,?int?size,?int?d) {//循環1，控制步長變化，直到步長為1也執行后結束for?(int?increment?=?d;?increment?>?0;?increment?/=?2){//循環2，找出每組的開頭for?(int?k?=?0;?k?<?increment;?k++){//循環3，屬于選擇排序范圍了，對上面提供的開頭的組內元素做選擇排序for?(int?i?=?k;?i?<?size?-?1;?i?+=?increment){int?tempIndex?=?i;//循環4，屬于選擇排序for?(int?j?=?i?+?increment;?j?<?size;?j?+=?increment){if?(array[j]?<?array[tempIndex]){tempIndex?=?j;}}if?(tempIndex?!=?i){int?temp?=?array[i];array[i]?=?array[tempIndex];array[tempIndex]?=?temp;}}}} }

輔助的操作函數，包括 亂序函數，打印數組函數，交換元素值得函數

//交換函數 void?swap(int?*a,?int?*b) {int?c?=?*a;*a?=?*b;*b?=?c; } //亂序函數，通過從后往前遍歷數組，使得當前索引的值與隨機一個比它索引小的元素交換 void?shuffle(int?*array,?int?size) {srand((unsigned?int)time(NULL));for?(int?i?=?size?-?1;?i?>?0;?i--){int?index?=?rand()?%?i;swap(&array[i],?&array[index]);} } //打印數組函數 void?printArray(int?*array,?int?size) {for?(int?i?=?0;?i?<?size;?i++){printf("%d\t",array[i]);} }

主函數，負責測試各個排序函數

int?main() {//定義并初始化數組int?array[MAX]?=?{?0?};for?(int?i?=?0;?i?<?MAX;?i++){array[i]?=?i;}//對數組數據進行亂序shuffle(array,?MAX);//打印亂序后的數組printArray(array,?MAX);//測試各個排序的效果/*printf("\n快速排序后\n");quickSort(array,?0,?MAX?-?1);printArray(array,?MAX);*/printf("\nshell排序后\n");shellSort(array,?MAX,?MAX?/?2);printArray(array,?MAX);return?0; }

轉載于:https://my.oschina.net/u/2439195/blog/516372

總結

以上是生活随笔為你收集整理的常用高级排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。