冒泡算法

????????依次比較兩個相鄰的子元素，如果他們的順序錯誤就把他們交換過來，重復地進行此過程直到?jīng)]有相鄰元素需要交換，即完成整個冒泡，時間復雜度。

1. 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數(shù)；
3. 針對所有的元素重復以上的步驟，除了最后一個；
4. 重復步驟1~3，直到排序完成。

? ? ? ??

Java?

	/*** 冒泡排序* @param array* @return*/public static int[] bubbleSort(int[] array){if(array.length > 0){for(int i = 0;i<array.length;i++){for(int j = 0;j<array.length - 1 - i;j++){if(array[j] > array[j+1]){int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}}}return array;}

?????????優(yōu)化后，可減少循環(huán)次數(shù)

        //定義標志位，用于判定最外層每一輪是否進行了交換boolean flag = false;for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {//進入這個if分支里邊，則說明有元素進行了交換//所以將flag=trueflag = true;int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}//在進行一輪的排序后，判斷是否發(fā)生了元素是否交換；if (!flag) {// 沒有交換，數(shù)組已是有序，則結束排序；break;} else {//如果發(fā)生交換，將flag再次置為false，進行下一輪排序flag = false;}}

Python?

from typing import List# 冒泡排序
def bubble_sort(arr: List[int]):"""冒泡排序(Bubble sort):param arr: 待排序的List,此處限制了排序類型為int:return: 冒泡排序是就地排序(in-place)"""length = len(arr)if length <= 1:returnfor i in range(length):'''設置標志位，若本身已經(jīng)有序，則直接break'''is_made_swap = Falsefor j in range(length - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]is_made_swap = Trueif not is_made_swap:breakreturn arrif __name__ == '__main__':arr = bubble_sort([55, 34, 55, 33, 13, 45, 67])print(arr)

Js?

for(var i=0;i<arr.length-1;i++){//確定輪數(shù)for(var j=0;j<arr.length-i-1;j++){//確定每次比較的次數(shù)if(arr[j]>arr[j+1]){tem = arr[j];arr[j] = arr[j+1];arr[j+1] = tem;}}}

選擇排序

????????每一趟從待排序數(shù)組中選出最小的數(shù)字，按順序放在已經(jīng)排好序的數(shù)組的后面，直到全部排完。?時間復雜度：?空間復雜度：(常規(guī))

1. 初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空；
2. 第i趟排序(i=1,2,3…n-1)開始時，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區(qū)中-選出關鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)；
3. n-1趟結束，數(shù)組有序化了?

Java

private static Integer[] selectSort(Integer[] arr) {/*初始化左端、右端元素索引*/int left = 0;int right = arr.length - 1;while (left < right) {/*初始化最小值、最大值元素的索引*/int min = left;int max = right;for (int i = left; i <= right; i++) {/*標記每趟比較中最大值和最小值的元素對應的索引min、max*/if (arr[i] < arr[min])min = i;if (arr[i] > arr[max])max = i;}/*最大值放在最右端*/int temp = arr[max];arr[max] = arr[right];arr[right] = temp;/*此處是先排最大值的位置，所以得考慮最小值（arr[min]）在最大位置（right）的情況*/if (min == right)min = max;/*最小值放在最左端*/temp = arr[min];arr[min] = arr[left];arr[left] = temp;/*每趟遍歷，元素總個數(shù)減少2，左右端各減少1，left和right索引分別向內(nèi)移動1*/left++;right--;}return arr;}// 測試public static void main(String[] args) {Integer[] arr = new Integer[]{77, 22, 3, 4, 1, 44, 34, 41};Integer[] arrs = selectSort(arr);for (Integer integer : arrs) {System.out.println(integer);}}

Python?

def selectionSort(A):le = len(A)for i in range(le):  # 遍歷次數(shù)for j in range(i + 1, le):  # 查找待排序序列中的最小元素并交換if A[i] > A[j]:A[i], A[j] = A[j], A[i]print(A)tes = [22, 41, 55, 46, 4, 5, 3, 32, 454]
selectionSort(tes)  # [3, 4, 5, 22, 32, 41, 46, 55, 454]

Js?

var arr = [2, 8, 6, 2, 9, 7, 3, 11, 6]//從第0次開始for (var j = 0; j < arr.length - 1; j++) {var minIndex = jfor (var i = j + 1; i < arr.length; i++) {if (arr[i] < arr[minIndex]) minIndex = i}if (minIndex != j) {var tmp = arr[j]arr[j] = arr[minIndex]arr[minIndex] = tmp}
}console.log(arr)

插入排序

?????????將一個記錄插入到已經(jīng)排序好的有序表中，從而得到一個新的、記錄增加1的有序表。在實現(xiàn)過程中使用雙層循環(huán)，外層循環(huán)對除了第一個元素之外的所有元素，內(nèi)層循環(huán)對當前元素前面有序表進行待插入位置查找，進行移動。時間復雜度：?空間復雜度：(常規(guī))

1. 從第一個元素開始，該元素可以認為已經(jīng)被排序；
2. 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置；
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
5. 將新元素插入到該位置后；
6. 重復步驟2~5。

Java

?直接插入排序

public static void insertSort2 (int[] numbers) {//控制循環(huán)輪數(shù)for (int i = 1; i < numbers.length; i++) {int temp = numbers[i]; //定義待交換元素int j; //定義待插入的位置for (j = i; j > 0 && temp < numbers[j - 1]; j --) {numbers[j] = numbers[j - 1];}numbers[j] = temp;System.out.println("第" + i + "輪的排序結果為：" + Arrays.toString(numbers));}System.out.println("排序后的結果為：" + Arrays.toString(numbers));}

?折半插入排序

???????????在直接插入排序的基礎上，將查找方法從順序查找改為折半查找，就是在將 將要插入到現(xiàn)有 有序序列的數(shù)字尋找適當插入位置的比較次數(shù)減少了。

 private static void bInsertSort(int[] s){for(int i=1;i<s.length;i++){int temp=s[i];//保存要插入的數(shù)的數(shù)值int low=0;//設置查找區(qū)間初始值 下區(qū)間值int high=i-1;//上區(qū)間值while(low<=high){//查找結束條件int mid=(high+low)/2;//折半，中間值if(s[mid]>temp){//待插入值小于中間值high=mid-1;//上區(qū)間值變?yōu)橹虚g值-1}else {//待插入值大于中間值low=mid+1;//下區(qū)間值變?yōu)橹虚g值+1}}for (int j=i-1;j>=low;j--){s[j+1]=s[j];//將low及l(fā)ow之前的數(shù)向前移動一位}s[low]=temp;//low就是待插入值的適當插入點}System.out.println(Arrays.toString(s));//輸出排好序的數(shù)組}

Python

import pandas as pd
import random
import timeimport seaborn as sns
import matplotlib.pyplot as plt# 解決win 系統(tǒng)中文不顯示問題
from pylab import mpl
mpl.rcParams['font.sans-serif']=['SimHei']def insert_sort(tg_list):''' 排序算法：插入排序 '''for i in range(1,len(tg_list)):for j in range(i,0,-1):if tg_list[j] < tg_list[j-1]:tg_list[j-1], tg_list[j] = tg_list[j], tg_list[j-1]else:breakdef get_runtime(n):''' 獲取排序耗時 '''time_start = time.clock()  # 記錄開始時間list_ = [random.randint(1,n) for i in range(n)]insert_sort(list_)time_end = time.clock()  # 記錄結束時間time_sum = time_end - time_start  # 計算的時間差為程序的執(zhí)行時間，單位為秒/sreturn [n,time_sum]def plot(df):''' 繪制折線圖 '''pd.options.display.notebook_repr_html=False  # 表格顯示plt.rcParams['figure.dpi'] = 75  # 圖形分辨率sns.set_style(style='darkgrid')  # 圖形主題plt.figure(figsize=(4,3),dpi=150)sns.lineplot(data=df,x='數(shù)量',y='耗時(s)')if __name__ == "__main__":nums = range(100,10000,100)res = list(map(get_runtime,nums))res_df = pd.DataFrame(res,columns=['數(shù)量','耗時(s)'])plot(res_df)

Js?

   function insertSort(arr) {var len =arr.length;for (var i=1;i<len; i++) {var temp=arr[i];var j=i-1;//默認已排序的元素while (j>=0 && arr[j]>temp) {  //在已排序好的隊列中從后向前掃描arr[j+1]=arr[j]; //已排序的元素大于新元素，將該元素移到一下個位置j--;}arr[j+1]=temp;}return arr}

?二分插入排序

function binaryInsertSort(arr) {var len =arr.length;for (var i=1;i<len; i++) {var key=arr[i],left=0,right=i-1;while(left<=right){       //在已排序的元素中二分查找第一個比它大的值var mid= parseInt((left+right)/2); //二分查找的中間值if(key<arr[mid]){ //當前值比中間值小  則在左邊的子數(shù)組中繼續(xù)尋找   right = mid-1;}else{left=mid+1;//當前值比中間值大   在右邊的子數(shù)組繼續(xù)尋找}}              for(var j=i-1;j>=left;j--){arr[j+1]=arr[j];}arr[left]=key;}return arr;}    

快速排序

?????????每趟排序時選出一個基準值，然后將所有元素與該基準值比較，并按大小分成左右兩堆，然后遞歸執(zhí)行該過程，直到所有元素都完成排序。

1. 從數(shù)列中挑出一個元素，稱為 “基準”（pivot）；
2. 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；
3. 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序?

Java

    ##--------------------------第一版----------------------------------------public static void quickSort1(int[] arr) {if (arr == null || arr.length < 2) {return;}process1(arr, 0, arr.length - 1);}//第一版快排，這一版的時間復雜度為O(n2)public static void process1(int[] arr, int L, int R) {if (L >= R) {return;}//在[L,R]范圍上，根據(jù)arr[R]，模仿netherlandsFlag方法，//將數(shù)組分為三個部分：<=arr[R]的部分，arr[R]本身，>=//arr[R]的部分，這樣確定了在最終的數(shù)組中arr[R]的位置，//并返回這個位置int M = partition(arr, L, R);//接下來只要在左右兩側重復這個過程就行process1(arr, L, M - 1);process1(arr, M + 1, R);}public static int partition(int[] arr, int L, int R) {if (L > R) {return -1;}if (L == R) {return L;}int lessEqual = L - 1;int index = L;while (index < R) {if (arr[index] <= arr[R]) {swap(arr, index, ++lessEqual);}index++;}swap(arr, ++lessEqual, R);return lessEqual;}##--------------------------第二版----------------------------------------public static void quickSort2(int[] arr) {if (arr == null || arr.length < 2) {return;}process2(arr, 0, arr.length - 1);}//第二版快排：相比第一版的區(qū)別/優(yōu)勢：在于一次可以確定//相等基準值的一個區(qū)域，而不再只是一個值//第二版的時間復雜度為O(n2)public static void process2(int[] arr, int L, int R) {if (L >= R) {return;}int[] equalArea = netherlandsFlag(arr, L, R);process2(arr, L, equalArea[0] - 1);process2(arr, equalArea[1] + 1, R);}//這個方法的目的是按arr[R]為基準值，將arr數(shù)組劃分為小于基準值、//等于基準值、大于基準值三個區(qū)域//在arr[L...R]上，以arr[R]做基準值，在[L...R]范圍內(nèi)，<arr[R]的數(shù)//都放在左側，=arr[R]的數(shù)放在中間，>arr[R]的數(shù)放在右邊//返回的值為和arr[R]相等的范圍的數(shù)組public static int[] netherlandsFlag(int[] arr, int L, int R) {if (L > R) {return new int[] { -1, -1 };}if (L == R) {return new int[] { L, R };}//小于基準值的區(qū)域的右邊界int less = L - 1;//大于基準值的區(qū)域的左邊界int more = R;int index = L;while (index < more) {//等于基準值，不做處理，判斷下一個數(shù)據(jù)if (arr[index] == arr[R]) {index++;//當前數(shù)小于基準值} else if (arr[index] < arr[R]) {//將當前值和小于區(qū)域右邊的一個值交換：swap//判斷下一個數(shù)據(jù)：index++//小于區(qū)域右移：++less（先++是為了完成swap）swap(arr, index++, ++less);} else {//將當前值和大于區(qū)域左邊的一個值交換：swap//大于區(qū)域左移：--more（先--是為了完成swap）swap(arr, index, --more);}}//因為最開始是把arr[R]作為基準值的，所以在進行接下來的一步之前，//arr[R]實際是在大于區(qū)域的最右側的，所以還需要進行一步交換，這樣//整個數(shù)組就成了小于區(qū)域、等于區(qū)域、大于區(qū)域的樣子swap(arr, more, R);//less + 1是等于區(qū)域的起始位置，more經(jīng)過上一步的和arr[R]交換后，//就成了等于區(qū)域的結束位置return new int[] { less + 1, more };}##--------------------------第三版----------------------------------------public static void quickSort3(int[] arr) {if (arr == null || arr.length < 2) {return;}process3(arr, 0, arr.length - 1);}//第三版快排：不再固定去arr[R]，改為去隨機位置的值，然后//和arr[R]進行交換，接下來的過程就和第二版一樣//第三版的復雜度變化了，是O(nlogn)，該事件復雜度是最終求//的是數(shù)學上的一個平均期望值public static void process3(int[] arr, int L, int R) {if (L >= R) {return;}swap(arr, L + (int) (Math.random() * (R - L + 1)), R);int[] equalArea = netherlandsFlag(arr, L, R);process3(arr, L, equalArea[0] - 1);process3(arr, equalArea[1] + 1, R);}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

Python

# coding=utf-8
def quick_sort(array, start, end):if start >= end:returnmid_data, left, right = array[start], start, endwhile left < right:while array[right] >= mid_data and left < right:right -= 1array[left] = array[right]while array[left] < mid_data and left < right:left += 1array[right] = array[left]array[left] = mid_dataquick_sort(array, start, left-1)quick_sort(array, left+1, end)if __name__ == '__main__':array = [11, 14, 34, 7, 30, 14, 27, 45, 25, 5, 66, 11]quick_sort(array, 0, len(array)-1)print(array)

Js

function quickSort( arr ) {if(arr.length <= 1) return arr;const num = arr[0];let left = [], right = [];for(let i = 1;i < arr.length; i++) {if(arr[i]<=num) left.push(arr[i]);else right.push(arr[i]);}return quickSort(left).concat([num],quickSort(right));
}

堆排序

????????利用堆這種數(shù)據(jù)結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為0(nlogn)，它也是不穩(wěn)定排序。

1. 將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區(qū)；
2. 將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；
3. 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對當前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復此過程直到有序區(qū)的元素個數(shù)為n-1，則整個排序過程完成。

?

Java

 public static void sort(int []arr){//1.構建大頂堆for(int i=arr.length/2-1;i>=0;i--){//從第一個非葉子結點從下至上，從右至左調(diào)整結構adjustHeap(arr,i,arr.length);}//2.調(diào)整堆結構+交換堆頂元素與末尾元素for(int j=arr.length-1;j>0;j--){swap(arr,0,j);//將堆頂元素與末尾元素進行交換adjustHeap(arr,0,j);//重新對堆進行調(diào)整}}/*** 調(diào)整大頂堆（僅是調(diào)整過程，建立在大頂堆已構建的基礎上）* @param arr* @param i* @param length*/public static void adjustHeap(int []arr,int i,int length){int temp = arr[i];//先取出當前元素ifor(int k=i*2+1;k<length;k=k*2+1){//從i結點的左子結點開始，也就是2i+1處開始if(k+1<length && arr[k]<arr[k+1]){//如果左子結點小于右子結點，k指向右子結點k++;}if(arr[k] >temp){//如果子節(jié)點大于父節(jié)點，將子節(jié)點值賦給父節(jié)點（不用進行交換）arr[i] = arr[k];i = k;}else{break;}}arr[i] = temp;//將temp值放到最終的位置}/*** 交換元素* @param arr* @param a* @param b*/public static void swap(int []arr,int a ,int b){int temp=arr[a];arr[a] = arr[b];arr[b] = temp;}

Python

建堆-調(diào)堆-排序?

def heapify(unsorted, index, heap_size):largest = indexleft_index = 2 * index + 1right_index = 2 * index + 2if left_index < heap_size and unsorted[left_index] > unsorted[largest]:largest = left_indexif right_index < heap_size and unsorted[right_index] > unsorted[largest]:largest = right_indexif largest != index:unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]heapify(unsorted, largest, heap_size)
def heap_sort(unsorted):n = len(unsorted)for i in range(n // 2 - 1, -1, -1):heapify(unsorted, i, n)for i in range(n - 1, 0, -1):unsorted[0], unsorted[i] = unsorted[i], unsorted[0]heapify(unsorted, 0, i)return unsortedif __name__ == '__main__':test = [4,3,2,1]print(heap_sort(test))

Js

/*調(diào)整函數(shù)@param arr 待排序的數(shù)組@param i 表示等待調(diào)整的那個非葉子節(jié)點的索引@param length 待調(diào)整長度
*/
function adjustHeap(arr,i,length){var notLeafNodeVal = arr[i]; //非葉子節(jié)點的值//for循環(huán),k的初始值為當前非葉子節(jié)點的左孩子節(jié)點的索引//k = 2*k+1表示再往左子節(jié)點找for(var k=i*2+1;k<length;k=2*k+1){//如果k+1還在待調(diào)整的長度內(nèi)，且右子樹的值大于等于左子樹的值//將k++,此時為當前節(jié)點的右孩子節(jié)點的索引if(k+1<length && arr[k]<arr[k+1]){k++;}//如果孩子節(jié)點大于當前非葉子節(jié)點if(arr[k]>notLeafNodeVal){arr[i] = arr[k]; //將當前節(jié)點賦值為孩子節(jié)點的值i = k;//將i賦值為孩子的值,再看其孩子節(jié)點是否有比它大的}else{break; //能夠break的保證是：從左到右、從上到下進行調(diào)整//只要上面的不大于,下面的必不大于}}//循環(huán)結束后,將i索引處的節(jié)點賦值為之前存的那個非葉子節(jié)點的值arr[i] = notLeafNodeVal;
}//堆排序函數(shù)
function heapSort(arr){//進行第一次調(diào)整for(var i=parseInt(arr.length/2)-1;i>=0;i--){adjustHeap(arr,i,arr.length);}for(var j=arr.length-1;j>0;j--){/*進行交換:第一次調(diào)整的時候從左到右、從上到下的;交換時只是變動了堆頂元素和末尾元素,末尾元素不用去管,因為已經(jīng)是之前長度最大的了,只需要把當前堆頂元素找到合適的位置即可*/var temp = arr[j];arr[j] = arr[0];arr[0] = temp;adjustHeap(arr,0,j);}
}var arr = [0,2,4,1,5];
console.log("排序前的數(shù)組：",arr);
heapSort(arr);
console.log("排序后的數(shù)組：",arr);

希爾排序

????????插入排序的一種算法，先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序。時間復雜度O(N^1.3)

• 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列個數(shù)k，對序列進行k 趟排序；
• 每趟排序，根據(jù)對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

Java?

	   /*初始化劃分增量*/int increment = len;	int j,temp,low,mid,high;/*每次減小增量，直到increment = 1*/while (increment > 1){	/*增量的取法之一：除三向下取整+1*/increment = increment/3 + 1;/*對每個按增量劃分后的邏輯分組，進行直接插入排序*/for (int i = increment; i < len; ++i) {	low = 0;high = i-1;temp = arr[i];while(low <= high){mid = (low+high)/2;if(arr[mid]>temp){high = mid-1;}else{low = mid+1;}}j = i-increment;/*移動元素并尋找位置*/while(j >= high+1){	arr[j+increment] = arr[j];j -= increment;} /*插入元素*/arr[j+increment] = temp;	}}

Python

# 希爾排序
def shell_sort(input_list):# 希爾排序：三重循環(huán)，依次插入，直接插入法的優(yōu)化版l = input_list # 簡化參數(shù)名gaps = [701, 301, 132, 57, 23, 10, 4, 1] # Marcin Ciura's gap sequencefor gap in gaps:for i in range(gap, len(l)):insert_value = l[i] # 終止條件j = iwhile j >= gap and l[j - gap] > insert_value:l[j] = l[j - gap]j -= gapif j != i:l[j] = insert_value # 循環(huán)終止，插入值return l
'''# 另外一種寫法
def shell_sort(input_list):# 希爾排序：三重循環(huán)，依次插入，直接插入法的優(yōu)化版l = input_list # 簡化參數(shù)名gap = len(l) // 2 # 長度取半while gap > 0:for i in range(gap, len(l)):insert_value = l[i] # 終止條件j = iwhile j >= gap and l[j - gap] > insert_value:l[j] = l[j - gap]j -= gapif j != i:l[j] = insert_value # 循環(huán)終止，插入值gap //= 2return l
'''if __name__ == '__main__':test = [4,3,2,1]print(shell_sort(test))

Js

function shellSort(arr) {let len = arr.length;for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {for (let i = gap; i < len; i++) {let j = i;let current = arr[i];while (j - gap >= 0 && arr[j - gap] > current) {arr[j] = arr[j - gap];j = j - gap;}arr[j] = current;}}return arr;
}

歸并排序

????????歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個非常典型的應用。將已有序的子 序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序 表，稱為二路歸并。時間復雜度為O(nlogn)

• 把長度為n的輸入序列分成兩個長度為n/2的子序列；
• 對這兩個子序列分別采用歸并排序；
• 將兩個排序好的子序列合并成一個最終的排序序列。

Java?

public class Merge02 {private static Comparable[] assist;public void sort(Comparable[] arr) {assist = new Comparable[arr.length];sort(arr, 0, arr.length - 1);}public void sort(Comparable[] arr, int lo, int hi) {if (lo >= hi) {return;}int mid = lo + (hi - lo) / 2;sort(arr, lo, mid);sort(arr, mid + 1, hi);merge(arr, lo, mid, hi);}public void merge(Comparable[] arr, int lo, int mid, int hi) {int i = lo;int p1 = lo;int p2 = mid + 1;while (p1 <= mid && p2 <= hi) {if (arr[p1].compareTo(arr[p2]) > 0) {assist[i++] = arr[p2++];} else {assist[i++] = arr[p1++];}}while (p1 <= mid) {assist[i++] = arr[p1++];}while (p2 <= hi) {assist[i++] = arr[p2++];}for (int index = lo; index <= hi; index++) {arr[index] = assist[index];}}
}

Python

#merge的功能是將前后相鄰的兩個有序表歸并為一個有序表的算法。
def merge(left, right):ll, rr = 0, 0result = []while ll < len(left) and rr < len(right):if left[ll] < right[rr]:result.append(left[ll])ll += 1else:result.append(right[rr])rr += 1result+=left[ll:]result+=right[rr:]return resultdef merge_sort(alist):if len(alist) <= 1:return alistnum = len(alist) // 2   # 從中間劃分兩個子序列l(wèi)eft = merge_sort(alist[:num]) # 對左側子序列進行遞歸排序right = merge_sort(alist[num:]) # 對右側子序列進行遞歸排序return merge(left, right) #歸并tesl=[1,3,45,23,23,12,43,45,33,21]
print(merge_sort(tesl))
#[1, 3, 12, 21, 23, 23, 33, 43, 45, 45]

Js?

// 合并做分支數(shù)組和右分支數(shù)組，左分支和右分支在自己數(shù)組里面已經(jīng)是有序的。所以就方便很多。
function merge(left, right){// 剪枝優(yōu)化if(left[left.length -1] <= right[0]){return left.concat(right)}if(right[right.length-1] <= left[0]){return right.concat(left)}let tmp = [];let leftIndex =0, rightIndex = 0;while(leftIndex < left.length && rightIndex < right.length) {if(left[leftIndex] <= right[rightIndex]) {tmp.push(left[leftIndex]);leftIndex ++;}else{tmp.push(right[rightIndex]);rightIndex ++;}}// 最后，檢查一下是否有數(shù)組內(nèi)容沒有拷貝完if(leftIndex < left.length){tmp = tmp.concat(left.slice(leftIndex))}if(rightIndex < right.length){tmp = tmp.concat(right.slice(rightIndex))}return tmp;
}function mergeSort(arr){// 拆到只有一個元素的時候，就不用再拆了。if(arr.length <2){return arr;}const mid = arr.length/2;const left = arr.slice(0, mid);const right = arr.slice(mid);const leftSplited = mergeSort(left);const rightSplited = mergeSort(right);return merge(leftSplited, rightSplited);
}

?基數(shù)排序（Radix Sort）

? ? ? ? 基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前?；鶖?shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。?基數(shù)排序的平均時間復雜度為 O(nk)，k 為最大元素的長度，最壞時間復雜度為 O(nk)，空間復雜度為 O(n) ，是穩(wěn)定排序。

1. 取得數(shù)組中的最大數(shù)，并取得位數(shù)，即為迭代次數(shù)n（例如：數(shù)組中最大數(shù)為123，則 n=3）；
2. arr為原始數(shù)組，從最低位（或最高位）開始根據(jù)每位的數(shù)字組成radix數(shù)組（radix數(shù)組是個二維數(shù)組，其中一維長度為10），例如123在第一輪時存放在下標為3的radix數(shù)組中；
3. 將radix數(shù)組中的數(shù)據(jù)從0下標開始依次賦值給原數(shù)組；
4. 重復2~3步驟n次即可。

Java

public static void radixSort(int[] arr) {if (arr.length < 2) return;int maxVal = arr[0];//求出最大值for (int a : arr) {if (maxVal < a) {maxVal = a;}}int n = 1;while (maxVal / 10 != 0) {//求出最大值位數(shù)maxVal /= 10;n++;}for (int i = 0; i < n; i++) {List<List<Integer>> radix = new ArrayList<>();for (int j = 0; j < 10; j++) {radix.add(new ArrayList<>());}int index;for (int a : arr) {index = (a / (int) Math.pow(10, i)) % 10;radix.get(index).add(a);}index = 0;for (List<Integer> list : radix) {for (int a : list) {arr[index++] = a;}}}}

Python

def radix_sort(input_list):RADIX = 10placement = 1max_digit = max(input_list)while placement <= max_digit:buckets: list[list] = [list() for _ in range(RADIX)]for i in input_list:tmp = int((i / placement) % RADIX)buckets[tmp].append(i)a = 0for b in range(RADIX):for i in buckets[b]:input_list[a] = ia += 1# move to nextplacement *= RADIXreturn input_listif __name__ == '__main__':test = [4,3,2,1]print(radix_sort(test))

Js?

function radixSort(array) {let length = array.length;// 如果不是數(shù)組或者數(shù)組長度小于等于1，直接返回，不需要排序if (!Array.isArray(array) || length <= 1) return;let bucket = [],max = array[0],loop;// 確定排序數(shù)組中的最大值for (let i = 1; i < length; i++) {if (array[i] > max) {max = array[i];}}// 確定最大值的位數(shù)loop = (max + '').length;// 初始化桶for (let i = 0; i < 10; i++) {bucket[i] = [];}for (let i = 0; i < loop; i++) {for (let j = 0; j < length; j++) {let str = array[j] + '';if (str.length >= i + 1) {let k = parseInt(str[str.length - 1 - i]); // 獲取當前位的值，作為插入的索引bucket[k].push(array[j]);} else {// 處理位數(shù)不夠的情況，高位默認為 0bucket[0].push(array[j]);}}array.splice(0, length); // 清空舊的數(shù)組// 使用桶重新初始化數(shù)組for (let i = 0; i < 10; i++) {let t = bucket[i].length;for (let j = 0; j < t; j++) {array.push(bucket[i][j]);}bucket[i] = [];}}return array;
}

?桶排序（Bucket Sort）

????????計數(shù)排序的升級版。在額外空間充足的情況下，盡量增大桶的數(shù)量。使用的映射函數(shù)能夠?qū)⑤斎氲?strong>?N?個數(shù)據(jù)均勻的分配到?K?個桶中。?

????????設置一個bucketSize（該數(shù)值的選擇對性能至關重要，性能最好時每個桶都均勻放置所有數(shù)值，反之最差），表示每個桶最多能放置多少個數(shù)值；
????????遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)依次放到到對應的桶里去；
????????對每個非空的桶進行排序，可以使用其它排序方法（這里遞歸使用桶排序）；
????????從非空桶里把排好序的數(shù)據(jù)拼接起來即可。

Java

private static List<Integer> bucketSort(List<Integer> arr, int bucketSize) {int len = arr.size();if (len < 2 || bucketSize == 0) {return arr;}int minVal = arr.get(0), maxVal = arr.get(0);for (int i = 1; i < len; i++) {if (arr.get(i) < minVal) {minVal = arr.get(i);} else if (arr.get(i) > maxVal) {maxVal = arr.get(i);}}int bucketNum = (maxVal - minVal) / bucketSize + 1;List<List<Integer>> bucket = new ArrayList<>();for (int i = 0; i < bucketNum; i++) {bucket.add(new ArrayList<>());}for (int val : arr) {int idx = (val - minVal) / bucketSize;bucket.get(idx).add(val);}for (int i = 0; i < bucketNum; i++) {if (bucket.get(i).size() > 1) {bucket.set(i, bucketSort(bucket.get(i), bucketSize / 2));}}List<Integer> result = new ArrayList<>();for (List<Integer> val : bucket) {result.addAll(val);}return result;}

Python

def bucket_sort(input_list):l = input_listif not l:return []l_max, l_min = max(l), min(l)bucket_len = int(l_max - l_min) + 1buckets: list[list] = [[] for _ in range(bucket_len)]for i in l:buckets[int(i - l_min)].append(i)return [i for bucket in buckets for i in sorted(bucket)]if __name__ == '__main__':test = [4,3,2,1]print(bucket_sort(test))

Js?

function bucketSort(arr, bucketSize) {if (arr.length === 0) {return arr;}var i;var minValue = arr[0];var maxValue = arr[0];//求出最大值和最小值，這里有兩種方式，兩種方式只用其一，這里采用方式二。方式一：//for (i = 1; i < arr.length; i++) {//  if (arr[i] < minValue) {//      minValue = arr[i];                // 輸入數(shù)據(jù)的最小值// } else if (arr[i] > maxValue) {//     maxValue = arr[i];                // 輸入數(shù)據(jù)的最大值//  }//  }//方式二：maxValue = Math.max(...arr);minValue = Math.min(...arr);//桶的初始化var DEFAULT_BUCKET_SIZE = 5;            // 設置桶的默認數(shù)量為5bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  var buckets = new Array(bucketCount);for (i = 0; i < buckets.length; i++) {buckets[i] = [];}//利用映射函數(shù)將數(shù)據(jù)分配到各個桶中for (i = 0; i < arr.length; i++) {buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);}arr.length = 0;for (i = 0; i < buckets.length; i++) {insertionSort(buckets[i]);                      // 對每個桶進行排序，這里使用了插入排序，這里也可以直接用js的數(shù)組sort方法，很直接for (var j = 0; j < buckets[i].length; j++) {arr.push(buckets[i][j]);                      }}return arr;
}

?計數(shù)排序

????????計數(shù)排序是一種非基于比較的排序算法，其空間復雜度和時間復雜度均為O(n+k)，其中k是整數(shù)的范圍?；诒容^的排序算法時間復雜度最小是O(nlogn)的。

1. 找出數(shù)組中的最大值maxVal和最小值minVal；
2. 創(chuàng)建一個計數(shù)數(shù)組countArr，其長度是maxVal-minVal+1，元素默認值都為0；
3. 遍歷原數(shù)組arr中的元素arr[i]，以arr[i]-minVal作為countArr數(shù)組的索引，以arr[i]的值在arr中元素出現(xiàn)次數(shù)作為countArr[a[i]-min]的值；
4. 遍歷countArr數(shù)組，只要該數(shù)組的某一下標的值不為0則循環(huán)將下標值+minVal輸出返回到原數(shù)組即可。

Java

public static void countingSort(int[] arr) {int len = arr.length;if (len < 2) return;int minVal = arr[0], maxVal = arr[0];for (int i = 1; i < len; i++) {if (arr[i] < minVal) {minVal = arr[i];} else if (arr[i] > maxVal) {maxVal = arr[i];}}int[] countArr = new int[maxVal - minVal + 1];for (int val : arr) {countArr[val - minVal]++;}for (int arrIdx = 0, countIdx = 0; countIdx < countArr.length; countIdx++) {while (countArr[countIdx]-- > 0) {arr[arrIdx++] = minVal + countIdx;}}}

Python

def count_sort2(arr):maxi = max(arr)mini = min(arr)count_arr_length = maxi - mini + 1  # 計算待排序列表的數(shù)值區(qū)域長度，如4-9共9+1-4=6個數(shù)count_arr = [0 for _ in range(count_arr_length)]   # 創(chuàng)建一個全為0的列表for value in arr:count_arr[value - mini] += 1   # 統(tǒng)計列表中每個值出現(xiàn)的次數(shù)# 使count_arr[i]存放<=i的元素個數(shù)，就是待排序列表中比某個值小的元素有多少個for i in range(1, count_arr_length):count_arr[i] = count_arr[i] + count_arr[i - 1]new_arr = [0 for _ in range(len(arr))]   # 存放排序結果for i in range(len(arr)-1, -1, -1):    # 從后往前循環(huán)是為了使排序穩(wěn)定new_arr[count_arr[arr[i] - mini] - 1] = arr[i]   # -1是因為下標是從0開始的count_arr[arr[i] - mini] -= 1   # 每歸位一個元素，就少一個元素return new_arrif __name__ == '__main__':user_input = input('輸入待排序的數(shù)，用\",\"分隔:\n').strip()#strip() 方法用于移除字符串頭尾指定的字符（默認為空格）unsorted = [int(item) for item in user_input.split(',')]print(count_sort2(unsorted))

Js

function countingSort(arr, maxValue) {var bucket = new Array(maxValue+1),sortedIndex = 0;arrLen = arr.length,bucketLen = maxValue + 1;for (var i = 0; i < arrLen; i++) {if (!bucket[arr[i]]) {bucket[arr[i]] = 0;}bucket[arr[i]]++;}for (var j = 0; j < bucketLen; j++) {while(bucket[j] > 0) {arr[sortedIndex++] = j;bucket[j]--;}}return arr;
}
var arr = [2, 3, 8, 7, 1, 2, 7, 3];
console.log(countingSort(arr,8));//1,2,2,3,3,7,7,8

🌹 以上分享 10大常見排序算法，如有問題請指教寫。🌹🌹 如你對技術也感興趣，歡迎交流。🌹🌹🌹? 如有需要，請👍點贊💖收藏🐱?🏍分享?