冒泡排序的改良版
冒泡排序的改良版
循環(huán)優(yōu)化
外循環(huán)優(yōu)化
冒泡排序其實(shí)無需寫死排序arr.length-1趟，因?yàn)樵趯?duì)一些相對(duì)有序的數(shù)列進(jìn)行冒泡排序時(shí)，可能循環(huán)排序一遍這個(gè)數(shù)列就變得有序了，如：{1，2，3，4，5，7，6，8，9}，只需要7和6調(diào)換一次數(shù)列就有序了。只要一次冒泡的過程沒發(fā)生交換行為其實(shí)我們就可以判定這個(gè)數(shù)列是有序的了。
偽代碼
public static void sort(int[] arr){for(int i = 0;i<arr.length-1;i++){//外循環(huán)//使用一個(gè)標(biāo)記位flag標(biāo)記，初始化0int flag = 0;for(int j =0 ; j<arr.length-1;j++){if (arr[j]>arr[j+1]){//交換代碼//發(fā)生交換flag變1flag = 1;}}//判斷內(nèi)循環(huán)是否發(fā)生了交換行為if (flag == 0) return;}}內(nèi)循環(huán)優(yōu)化
在觀察冒泡排序時(shí)，可以發(fā)現(xiàn)每次內(nèi)循環(huán)一整趟執(zhí)行完后，數(shù)列中就會(huì)有一個(gè)較大的數(shù)就會(huì)沉到數(shù)列中他應(yīng)該到達(dá)的位置，如：假設(shè)一個(gè)無序的數(shù)列中有A,B,C三個(gè)數(shù)，并且A,B,C是數(shù)列中最大的三個(gè)數(shù)，有A>B>C，并且這三個(gè)數(shù)現(xiàn)在并不在它們數(shù)列中應(yīng)該在的位置（數(shù)列后三位）那么第一趟排序后，A肯定沉到最低下，其次是B,C。那么冒泡排序的最后一趟交換確定了數(shù)列中有序和無序的邊界，所以我們內(nèi)循環(huán)只需循環(huán)無序的那一邊就可以了，無需整個(gè)數(shù)列進(jìn)行循環(huán)。
偽代碼
public static void sort(int[] arr){//記錄最后交換位置int k = arr.length-1;for(int i = 0;i<arr.length-1;i++){//定義一個(gè)pos，來記錄最新交換位置int pos = 0;//根據(jù)最后交換位置k來優(yōu)化內(nèi)循環(huán)for(int j =0 ; j<k;j++){if (arr[j]>arr[j+1]){//交換代碼//交換完后記錄一下位置pos = j;}}//將最后的交換位置給kk = pos;}}內(nèi)外循環(huán)結(jié)合代碼
public static void sort(int[] arr){int pos=0,k=arr.length-1;for(int i = 0;i<arr.length-1;i++){int flag = 0;for(int j =0 ; j<k;j++){if (arr[j]>arr[j+1]){int tem = arr[j];arr[j] = arr[j+1];arr[j+1] = tem;pos = j;flag = 1;}}if (flag == 0) return;k = pos;}}總結(jié)
