交换排序算法

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

输出：这里写图片描述