交換排序算法

2019-11-06 06:25:06

字體：大中小

來源：轉載

供稿：網友

快速排序：為啥叫快速排序，因為速度快，效率高 1.先找一個數作為基準。 作為基準的這個數，一趟排下來，左邊的數必小于它，右邊的數必大于它，也就是說，它找到了自己的位置。 2.將兩個指針i，j分別指向表的起始（基準）和最后的位置。 3.比較j指針的數字是否小于基準，j–,直到j小于基準，交換位置 4.比較i指針的數字是否大于基準，i++,直到i大于基準，交換位置 5.若i==j，一趟排序完成。保證了基準的左邊比它小，右邊比它大（圖片來自網絡，我稍作修改）這里寫圖片描述

public class S{ public static int [] quick(int [] arr,int i,int j) { if(i < j) { int key = arr[i]; //使用left,right儲存 i,j 以便完成一次排序后繼續遞歸 int left =i; int right=j; while(left < right) { //若i<j 并 arr[j]>基準 while(left < right && arr[right] > key) { right--; } arr[left] = arr[right]; //若i<j 并 arr[i]<基準 while(left <right && arr[left] < key) { left++; } arr[right] = arr[left]; } arr[left] = key; System.out.PRintln( ); for(int x:arr) { System.out.print(x+" "); } //現在基準找到位置 //將基準左邊的繼續快排 quick(arr,i,right-1); //將基準右邊的繼續快排 quick(arr,left+1,j); } return arr; } public static void main (String[] args){ int []arr={8,1,0,4,6,2,7,9,5,3}; int len=arr.length-1; quick(arr,0,len); System.out.println(); System.out.println("最終："); for(int i:arr) { System.out.print(i+" "); } }}

輸出：這里寫圖片描述最好的情況：O(nlogn); 最壞的情況：O(n^2); 平均時間復雜度為O(nlogn)。但是不穩定. (若有兩個數相等，但是還交換了位置，則稱不穩定)

冒泡排序 冒泡排序和上一個快速排序都為交換排序都是通過比較并交換位置完成的。 1.從頭開始，依次比較相鄰連個數大小，i>i+1，則交換兩個位置； 2.一趟完成后，保證了最后一個數為最大值； 3.除過最后一個，從頭開始比較相鄰兩個數大小；這里寫圖片描述

public class S{ public static int [] quick(int [] arr) { int len=arr.length; // i 是用來固定每趟排序后最后幾位 for(int i=0;i<len-1;i++) { // j從0號下標開始,比較除了(最大下標-i)后的幾位 for(int j=0;j<len-i-1;j++) { //比較大小并交換 if(arr[j]>arr[j+1]) { int tmp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=tmp; } } System.out.print("第"+(i+1)+"趟 "); for(int x:arr) { System.out.print(x+" "); } System.out.println( ); } return arr; } public static void main (String[] args){ int []arr={3,6,4,2,11,10,5}; quick(arr); System.out.println("最終："); for(int i:arr) { System.out.print(i+" "); } }}

輸出：這里寫圖片描述