交換排序算法

2019-11-06 06:35:47

字體：大中小

來源：轉載

供稿：網友

快速排序：為啥叫快速排序，因為速度快，效率高 1.先找一個數(shù)作為基準。 作為基準的這個數(shù)，一趟排下來，左邊的數(shù)必小于它，右邊的數(shù)必大于它，也就是說，它找到了自己的位置。 2.將兩個指針i，j分別指向表的起始（基準）和最后的位置。 3.比較j指針的數(shù)字是否小于基準，j–,直到j小于基準，交換位置 4.比較i指針的數(shù)字是否大于基準，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 以便完成一次排序后繼續(xù)遞歸 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+" "); } //現(xiàn)在基準找到位置 //將基準左邊的繼續(xù)快排 quick(arr,i,right-1); //將基準右邊的繼續(xù)快排 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)。但是不穩(wěn)定. (若有兩個數(shù)相等，但是還交換了位置，則稱不穩(wěn)定)

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

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+" "); } }}

輸出：這里寫圖片描述