文章目錄

• • 1.總覽
  • 1.待操作數(shù)組
  • 2.直接插入排序（O(n²)）
  • 3.希爾排序
  • 4.直接選擇排序
  • 5.堆排序
  • • 5.1.堆的分類
    • 5.2.原理：
    • 5.3. 堆排序方法：
  • 6.冒泡排序
• 7.快速排序
• 8.歸并排序
• 9.基數(shù)排序

1.總覽

1.待操作數(shù)組

private static int[] ori = {30, 70, 40, 60, 10, 90, 20, 50, 80, 100};

2.直接插入排序（O(n²)）

原理：當(dāng)插入第i個元素時，R₁，R₂ … R_i-1已經(jīng)基本有序，將i元素和R₁，R₂ … R_i-1比較，插入合適的位置。

實現(xiàn)一（原理直譯成代碼，用兩個數(shù)組，將原數(shù)組元素逐個插入新數(shù)組）：

public static int[] straightInsertionSort(int[] ori) {//初始化sortint [] sort = new int[ori.length];//逐個將ori元素插入sortfor (int i = 0; i < ori.length; i++) {int ele = ori[i];if(i == 0){//sort 為空，ele 放入第一位置sort[0] = ele;}else {//sort 不為空，ele 與 sort 逐個比較for (int j = 0; j < sort.length; j++) {if(ele<sort[j]){//ele 小于 當(dāng)前sort，ele 放入當(dāng)前位置，sort 其余值后移for (int k = sort.length-1 ; k>j ; k--){sort[k] = sort[k-1];}sort[j] =ele;break;}else if(0==sort[j+1]){ //由于int數(shù)組初始化后，每一位默認(rèn)值都是0，如果下一位為0，當(dāng)前位就是最后一位//ele 比sort最后一個元素大，放入最后一個位置sort[j+1] =ele;break;}else {//比當(dāng)前sort大，且當(dāng)前sort不是最后一個值，就和下一個sort比較continue;}}}}return sort;}

3.希爾排序

原理：R₁，R₂ … R_i-1，取一個小于i的整數(shù)d₁作為第一個增量，將所有距離間隔d₁的元素放到一組（頭和尾，不包括中間），組內(nèi)直接選擇排序；然后取第二個增量d₂<d₁重復(fù)分組和排序，直至d_t=1；

4.直接選擇排序

原理：R₁，R₂ … R_i-1，將最小的元素與第1個位置元素交換；在剩余其他元素中選出最小的元素與第2個位置交換；…直至整體都排列好。

public static int[] straightSelectSort(int[] ori) {int minIndex = 0;//最小數(shù)值角標(biāo)int temp = 0;//交換臨時空間for (int i = 0; i < ori.length; i++) {minIndex = i;//最小數(shù)值角標(biāo)初始化為當(dāng)前i//當(dāng)前剩余未排序的數(shù)組中 選出最小的元素的角標(biāo)for (int j = i + 1; j < ori.length; j++) {if (ori[minIndex] > ori[j]) {minIndex = j;}}//將最小位置與當(dāng)前第i位交換temp = ori[i];ori[i] = ori[minIndex];ori[minIndex] = temp;}return ori;}

5.堆排序

5.1.堆的分類

大頂堆：所有父節(jié)點都比子節(jié)點大；用于從大到小排列；
小頂堆：所有父節(jié)點都比子節(jié)點小；用于從小到大排列；

5.2.原理：

R₁，R₂ … R_i-1，將所有元素構(gòu)建成小頂堆，取出根節(jié)點即為最小值。重新調(diào)整堆結(jié)構(gòu)，再取出根節(jié)點即為次小值…堆排序適合取出前n個值。

5.3. 堆排序方法：

小頂堆的構(gòu)造方法：先將所有值最為節(jié)點構(gòu)成完全二叉樹，從最后一個節(jié)點到根節(jié)點，根據(jù)小頂堆的調(diào)整方法調(diào)整；
小頂堆的排序方法：取出根節(jié)點后，把完全二叉樹的最后一個節(jié)點放到根節(jié)點的位置，從根節(jié)點開始，根據(jù)小頂堆的調(diào)整方法調(diào)整；
小頂堆的調(diào)整方法：檢查當(dāng)前左右子節(jié)點是否都比根節(jié)點大，不滿足，則交換最小子節(jié)點與父節(jié)點的位置。如果調(diào)整后子節(jié)點不為葉子節(jié)點，則遞歸調(diào)整以該葉子節(jié)點為根節(jié)點的樹；

在這里插入代碼片

6.冒泡排序

原理：相鄰的元素進(jìn)行比較和交換，將排序碼小的元素逐漸從底部移到頂部；整個過程就像是水底的氣泡逐漸上冒；

public static void bubbleSort(int[] ori){int temp = 0;//外層循環(huán)，每次循環(huán)都選出一個最大得放置在數(shù)組最后for (int i = 0; i < ori.length-1; i++) {//內(nèi)層循環(huán)，數(shù)組末尾放置好的元素不在動for (int j = 0; j < ori.length-1-i; j++) {if (ori[j] > ori[j+1]) {//相鄰兩個數(shù)比較，大的右移temp = ori[j];ori[j] = ori[j+1];ori[j+1] =temp;}}}}

7.快速排序

原理：
分治法（將原問題分解成若干規(guī)模更小單結(jié)構(gòu)和原問題相似的子問題，通過遞歸的解決子問題，將子問題的解組合成原問題的解）
第一步：待排序數(shù)組中 ，取一個數(shù)作為基準(zhǔn)，將所有記錄分成兩組，第1組都小于基準(zhǔn)，第2組都大于基準(zhǔn)；
第二布：采用相同的方法對左右兩組進(jìn)行排序，直到所有記錄排到相應(yīng)的位置；

/** @Description: 快速排序* @param arr: 待排序數(shù)組* @param begin: 開始元素角標(biāo)* @param end: 末尾元素角標(biāo)* @return void* @see*/private static void quickSort(int[] arr, int begin, int end) {if(begin<end){int index = patition(arr,begin,end);//基準(zhǔn)角標(biāo)（index左側(cè)元素都比arr[index]小，index右側(cè)元素都比arr[index]大）quickSort(arr,begin,index-1);//遞歸對分區(qū)的左側(cè)快速排序quickSort(arr,index+1,end);//遞歸對分區(qū)的右側(cè)快速排序}}/** @Description: 以最后一個元素最為元素基準(zhǔn)，將數(shù)組分冊兩個區(qū)域* @param arr: 帶分區(qū)數(shù)組* @param begin: 開始元素角標(biāo)* @param end: 末尾元素角標(biāo)* @return int 基準(zhǔn)角標(biāo)* @see*/private static int patition(int[] arr, int begin, int end) {int index = begin-1;//基準(zhǔn) 初始角標(biāo)int patition = arr[end];//基準(zhǔn)數(shù)值 取最后一個元素的值for (int i = begin; i <= end-1; i++) {if(arr[i]<=patition){//當(dāng)前值比基準(zhǔn)值小index++;//index角標(biāo)右移一位swap(arr,i,index);//把當(dāng)前元素和index元素的數(shù)值交換}}//index角標(biāo)右移一位的角標(biāo)，就是第一個比基準(zhǔn)數(shù)值大的元素，交換兩者位置，就實現(xiàn)了快速排序的分區(qū)swap(arr,++index,end);return index;}/** @Description: 交換數(shù)組兩個元素的數(shù)值*/private static void swap(int[] arr, int x, int y) {int temp = arr[x];arr[x] = arr[y];arr[y] = temp;}

8.歸并排序

原理：先將整個待排序數(shù)組分成若干子表；完成子表內(nèi)的排序；將兩個或兩個以上的有序子表合并成一個新的有序表（合并過程：比較A[i]和B[j]的排序碼，將較小的元素復(fù)制到R[k]中，并令i（或j）和k分別加1，如此循環(huán)下去，知道A或B比較復(fù)制完，將另一個有序表剩余元素復(fù)制到R中）；

9.基數(shù)排序

原理：適用于元素很多，但是關(guān)鍵字很少的序列；例如，多個百以內(nèi)的數(shù)字排序，關(guān)鍵字只有三個，個位，十位，百位。

總結(jié)

以上是生活随笔為你收集整理的软考 - 排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。