-
這里先提一下最簡單的排序問題的區(qū)別
通過一個指針指向最后一個元素的位置，每次都是首元素依次與后面的元素比較然后根據(jù)大小交換，直到與指針位置的元素比較完畢，然后這個指針向前移動一個位置進行下一個子循環(huán)，直到指針移到首元素位置。
1.冒泡排序
代碼如下
package paixu;
public class BubbleSort {
public static void bubblesort(int []array){
int b=0;
for (int i = array.length-1;i>=0; i --) {
for(int j=0;j< i;j++){
if(array[j]>array[j+1]){
swap(array,j,j+1);
}
}
}
}
public static void swap(int[]arr,int a,int b)
//注意要數(shù)組傳進交換函數(shù)來
{
int temp =arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void main(String[] args) {
int []array1={1,2,3,6,3,5};
bubblesort(array1);
for (int i = 0; i < array1.length; i++) {
System.out.println(array1[i]);
}
}
}
2.選擇排序
public class SelectSort {
public static void sort(int []arr){
if (arr.length<2||arr==null)return;
for (int i = 0; i < arr.length-1; i++) {
int min=i;
for (int j=i+1;j<arr.length;j++){
if(arr[j]<arr[min])min=j;
}
swap(arr,i,min);
}
}
public static void swap(int[] arr,int a,int b){
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void main(String[] args){
int []array={1,2,1,6,3,4,2};
sort(array);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
}
3.插入排序
插入排序類似于整理撲克牌，基本操作是將一個記錄插入到已經排好序的有序數(shù)列中，從而得到一個有序但記錄數(shù)加一的有序數(shù)列。
public class InsertSort {
public static void sort(int []arr){
if (arr.length<2||arr==null)return;
for (int i = 1; i < arr.length; i++) {
for (int j=i-1;j>=0;j--){
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
public static void swap(int[] arr,int a,int b){
int temp=0;
temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void main(String[] args){
int []array={1,2,1,6,3,4,2};
sort(array);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
}
-
關于以上的三種簡單排序的復雜度計算
1.冒泡排序
第一次冒泡循環(huán)n次，然后然后每次冒泡比之前循環(huán)次數(shù)－1（因為指針向前移動了一位）
n+n-1+n-2+....+1=((1+n)n)1/2=1/2n+1/2n^2
T(1/2n+1/2n^2)= O(n^2)
2.選擇排序同理
3.插入排序每次插入比較的過程都是和指針位置前面的元素依次比較，
即：
0+1+2+...+n-1+n=((1+n)n)1/2=1/2n+1/2n^2
T(1/2n+1/2n2)=O(n2)
-
關于排序的穩(wěn)定性
穩(wěn)定性是指把排序后相同的元素的位次同排序前沒有改變
那穩(wěn)定了有什么好處呢？
我們來想一個工作場景，給你一個表格上面是面試的人基本信息有姓名，年齡，畢業(yè)學校。我先通過其畢業(yè)學校的排名對這個列表排序，然后在通過年齡進行排序。這樣如果排序算法穩(wěn)定，之前通過學校排名進行的排序的結果 ，就會在年齡相同的人中體現(xiàn)出來。
顯而易見冒泡排序和插入排序是穩(wěn)定的,而選擇排序是不穩(wěn)定的，是因為選擇排序的交換過程可能會把第一位次的元素換到第二位次。
舉個例子
序列5 8 5 2 9， 這個在執(zhí)行選擇排序的時候，第一遍，肯定會將array[0]=5，交換到2所在的位置，也就是 2 8 5 5 9，那么很顯然，之后的排序我們就會發(fā)現(xiàn)，array[2]中的5會出現(xiàn)在原先的array[0]之前，所以選擇排序不是一個穩(wěn)定的排序
- 關于寫好的算法的測試方法
因為有些方法是易想難證的，所以在打比賽時可以通過大量的數(shù)據(jù)模擬進行驗證，我們也管他叫做對數(shù)器。
它的思想是這樣的
我們先寫一個時間復雜度高但是絕對正確的算法，再把我們希望測試的算法放在里面，通過隨機數(shù)產生多組測試數(shù)據(jù)，然后通過比較兩個算法的結果，來確定算法的正確性。
import java.lang.reflect.Array;
import java.util.Arrays;
public class Logarithm {
public static void TestMethod(int []arr){
if (arr.length<2||arr==null)return;
for (int i = 1; i < arr.length; i++) {
for (int j=i-1;j>=0;j--){
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
public static int [] GenerateRandeoArray(int size ,int value){
int []arr= new int[(int)((size+1)*Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i]=((int) (Math.random() * (value + 1)) -(int)(Math.random()*value));
}
return arr;
}
//(value+1)*random()一定比value+1小，強制轉換為int 則其范圍為【0~value】了
public static void AbsoultRightMethod(int []arr){
Arrays.sort(arr);
}
public static int[]CopyArray(int[]arr){
if(arr==null)return null;
int []res=new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i]=arr[i];
}
return res;
}
public static boolean IsEqual(int[]arr1,int []arr2){
if (arr1==null&&arr2!=null)return false;
if (arr2==null&&arr1!=null)return false;
if (arr1==null&&arr2==null)return true;
for (int i = 0; i < arr1.length; i++) {
if(arr1[i]!=arr2[i])return false;
}return true;
}
public static void swap(int[] arr,int a,int b){
int temp=0;
temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void main(String[] args) {
boolean success=true;
int testtime=1;
for (int i = 0; i < testtime; i++) {
int[] array1=GenerateRandeoArray(100,20);
int[]array2=CopyArray(array1);
AbsoultRightMethod(array2);
TestMethod(array1);
if(!IsEqual(array1,array2)){
success=false;
break;
}
for (int i1 = 0; i1 < array1.length; i1++) {
System.out.print(array1[i1]);
}
System.out.println();
for (int i2 = 0; i2 < array2.length; i2++) {
System.out.print(array2[i2]);
}
System.out.println();
} System.out.println(success?"yes":"no");
}
}
關于二分歸并排序
- 這里首先要提一下的是遞歸思想
1.首先要知道函數(shù)的間調用是一個進棧出棧的過程
public class Stack {
public static int method1(){
method2();
return 0;
}
public static int method2(){
method3();
return 0;
}
public static int method3(){
method4();
return 0;
}
public static int method4(){
return 0;
}
}
棧
調用method1的時候method1以及其參數(shù)進棧，method1調method2的時候method2進棧......直到method4進棧。
然后method4執(zhí)行完畢后會被彈出，這時method3繼續(xù)執(zhí)行，即執(zhí)行調用了method4后的return 0;語句,然后將method3彈出.......直到所有函數(shù)都彈出，程序結束。
2.進行遞歸調用時也是這個道理，遞歸函數(shù)調用自己，把此時這個函數(shù)的個哥參數(shù)封存到棧底，然后它的子遞歸函數(shù)進棧，子遞歸函數(shù)調用自己的子函數(shù)...直到到達遞歸出口，即最頂端的子函數(shù)彈出，在其下面封存的函數(shù)被激活，執(zhí)行，彈出，再到下一個函數(shù)激活......直到整個程序結束。
3.二分歸并函數(shù)
前面提到的基本排序函數(shù)都是要一個數(shù)與剩下的數(shù)都比個遍，而二分的思想是我能不能把整體分成一半，在一半中進行比較，都比較完后我再把他們一次的整理下就好了。然后對于每個被分成一半的數(shù)我把他們看成一個整體再繼續(xù)劃分。這樣我比較的次數(shù)就大大減少了。
這是加入了對數(shù)器測試的代碼
import java.lang.reflect.Array;
import java.util.Arrays;
public class Logarithm {
public static int merge(int []arr ,int l,int r){
if(l==r)return 0;
int mid =l+((r-l)>>1);
return merge(arr,l,mid)+merge(arr,mid+1,r)+mergesort(arr,l,mid,r);
}
public static int mergesort(int []arr,int l,int m,int r){
int []help=new int [r-l+1];
int i=0;
int p1=l;
int p2=m+1;
//int res=0;
while(p1<=m&&p2<=r){
// res+=arr[p1]<arr[p2]?arr[p1]*(r-p2+1):0;
help[i++]=arr[p1]>arr[p2]?arr[p2++]:arr[p1++];
}
while(p1<=m){
help[i++]=arr[p1++];
}
while(p2<=r){
help[i++]=arr[p2++];
}
for ( i = 0; i < help.length; i++) {
arr[l+i]=help[i];
}
return 0;
}
public static int TestMethod(int []arr){
if (arr == null || arr.length < 2) {
return 0;
}
return merge(arr, 0, arr.length - 1);
}
public static int [] GenerateRandeoArray(int size ,int value){
int []arr= new int[(int)((size+1)*Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i]=((int) (Math.random() * (value + 1)) -(int)(Math.random()*value));
}
return arr;
}
//(value+1)*random()一定比value+1小，強制轉換為int 則其范圍為【0~value】了
public static void AbsoultRightMethod(int []arr){
Arrays.sort(arr);
}
public static int[]CopyArray(int[]arr){
if(arr==null)return null;
int []res=new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i]=arr[i];
}
return res;
}
public static boolean IsEqual(int[]arr1,int []arr2){
if (arr1==null&&arr2!=null)return false;
if (arr2==null&&arr1!=null)return false;
if (arr1==null&&arr2==null)return true;
for (int i = 0; i < arr1.length; i++) {
if(arr1[i]!=arr2[i])return false;
}return true;
}
public static void swap(int[] arr,int a,int b){
int temp=0;
temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void main(String[] args) {
boolean success=true;
int testtime=100;
for (int i = 0; i < testtime; i++) {
int[] array1=GenerateRandeoArray(100,20);
int[]array2=CopyArray(array1);
AbsoultRightMethod(array2);
TestMethod(array1);
if(!IsEqual(array1,array2)){
success=false;
break;
}
for (int i1 = 0; i1 < array1.length; i1++) {
System.out.print(array1[i1]);
}
System.out.println();
for (int i2 = 0; i2 < array2.length; i2++) {
System.out.print(array2[i2]);
}
System.out.println();
} System.out.println(success?"yes":"no");
}
}
4.關于遞歸問題的復雜度分析
這里引入一個計算遞歸問題復雜度的公式，有興趣的朋友可以去自行證明這里證明就不再多提。
master公式的使用
T(N) = a*T(N/b) + O(N^d)
a為一次遞歸調用分出子問題的個數(shù)
b為每個子問題的數(shù)據(jù)量
c為普通邏輯語句的個數(shù)
- log(b,a) > d -> 復雜度為O(N^log(b,a))
- log(b,a) = d -> 復雜度為O(N^d * logN)
- log(b,a) < d -> 復雜度為O(N^d)
那么二分歸并排序的Tn=1/2T(N/2)+O(N)
所以起時間復雜度為N*log(N)
好了接下來我們用這種思想試著解決一個問題
小和問題
在一個數(shù)組中，每一個數(shù)左邊比當前數(shù)小的數(shù)累加起來，叫做這個數(shù)組的小和。求一個數(shù)組的小和。
例子：
[1,3,4,2,5]
1左邊比1小的數(shù)，沒有；
3左邊比3小的數(shù)，1；
4左邊比4小的數(shù)，1、3；
2左邊比2小的數(shù)，1；
5左邊比5小的數(shù)，1、3、4、2；
所以小和為1+1+3+1+1+3+4+2=16
最簡單的想法是寫個雙重循環(huán)把它依次的遍歷
public static int comparator(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int res = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
res += arr[j] < arr[i] ? arr[j] : 0;
}
}
return res;
}
但再想想呢 有沒有更緊單些的復雜度更低的方法呢
我們之前 在分析二分歸并函數(shù)的時候 就寫到當一個東西從整個的循環(huán)遍歷它來進行交換的時候，這樣做是很低效的。而我們用二分的思想進行劃分的話可以復雜度從O(n^2)降到O（n*logn）。而對于這個問題可以這樣想嗎？
仔細想過程會發(fā)現(xiàn) 每次劃分都是有一左一右的，而且歸并的時候會有左右兩邊大小的比較，那么我們在每次比較的時候用一個變量記下左邊小的情況 然后進行累加，得出結果。
public class Code_SmallSum {
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return mergeSort(arr, 0, arr.length - 1);
}
public static int mergeSort(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int mid = l + ((r - l) >> 1);
return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}
public static int merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
int res = 0;
while (p1 <= m && p2 <= r) {
res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
return res;
}
// for test
public static int comparator(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int res = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
res += arr[j] < arr[i] ? arr[j] : 0;
}
}
return res;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (smallSum(arr1) != comparator(arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}https://www.keybr.com/
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
}
快速排序
- 在說快排前我們先去思考一個經典的荷蘭國旗問題
1.題目
給定一個數(shù)組arr，和一個數(shù)num，請把小于num的數(shù)放在數(shù)組的
左邊，等于num的數(shù)放在數(shù)組的中間，大于num的數(shù)放在數(shù)組的
右邊。
要求額外空間復雜度O(1)，時間復雜度O(N)
不言而喻
2.思考過程
很簡單 我們通過設置三個指針 分別指向數(shù)組外的兩端
以代表我們規(guī)劃大于num和小于num的區(qū)域
再有一個指針指向數(shù)組第一個元素進行遍歷
如果不等于num就與劃分區(qū)域附近的元素（或左或右）進行交換
等于的話就跳過
3.實現(xiàn)過程中遇到的麻煩
1最開始習慣性的用了for去做便利指針的移動，但發(fā)現(xiàn)指針的移動是有多種條件的 不適合for
2對從后面還來的數(shù)還需要判斷，通過指針的不動解決
3.通過限定i++的條件 即只有和自己或者相等的元素交換才能++ 來保證區(qū)域的劃分
public class flag {
public static void Flag(int[] arr, int num) {
int small = -1;
int big = arr.length;
int i = 0;
while (i < big)//
{//通過指針的不動來控制下一次循環(huán)依舊從該位置進行判定
if (arr[i] <num) {
swap(arr, i++, ++small);//對換過來的數(shù)已經進行了限定，
//即限定了小于區(qū)域后面得數(shù)只可能是等于區(qū)域的數(shù)或者我自己，
//如果是大于區(qū)域的數(shù)就會重新考慮
} else if (arr[i] > num) {
swap(arr, --big, i);//通過指針的停留重新考錄換過來的數(shù)
} else {
i++;
}
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String[] args) {
int a[] = {1, 3, 2, 6, 6, 236};
Flag(a,5);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}
}
}
快速排序中就是通過運用荷蘭國旗問題不斷地把數(shù)組化為
一邊<num一邊>num中間等于的部分不動支隊兩邊遞歸
如果說二分歸并排序運用了遞歸溯洄的時候那么快排則是運用了遞歸函數(shù)不斷地向下劃分的過程每次向下遞歸時我都把你先分成一半比一個數(shù)小一般比一個數(shù)大。
public class QuickSort {
public static int [] partion(int arr[],int l,int r ){
int small=l-1;
int big=r+1;
while(l<r){
if (arr[l]<arr[r-1]){
swap(arr,++small,l++);
}
else if (arr[l]>arr[r-1]){
swap(arr,--big,l);
}
else l++;
}
int []help=new int [2];
help[0]=small;
help[1]=big;
return help;
}
public static void quick (int []arr,int l,int r){
int []help=partion(arr, l,r);
if(l>=r)return;
quick(arr,l,help[0]+1);//注意這里help返回的是big和small，
quick(arr,help[1]-1,r);
}
public static void swap(int []arr,int a,int b){
int temp =arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void main(String[] args) {
int []a={1,3,9,1,4,3,5,3};
quick(a,0,a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
4.這里要提的一句是程序的運行是與數(shù)據(jù)有關系的，每次進行劃分的時候我們都是按照最后一個數(shù)進行劃分的，那么問題來了。如果數(shù)據(jù)是2，3，4，5，6，1呢 我們需要一直從頭遍歷，怎么解決這樣的問題呢？
很簡單在劃分前把最后一個數(shù)與前面隨機一個數(shù)交換就好了。
代碼如下
public class QuickSort1 {
public static int []partion (int []arr,int l,int r){
int small=l-1;
int big=r+1;//小錯
while(l<big){//不思考就寫習慣性的出寫了l<r
if(arr[l]<arr[r]){
swap(arr,++small,l++);
}
else if ((arr[l])>arr[r]){
swap(arr,--big,l);
}
else{
l++;
}
}
int []help=new int [2];
help[0]=small;
help[1]=big;
return help;
}
public static void QuickSort(int []arr,int l,int r){
if(l>=r)return;
swap(arr,l+(int)((r-l+1)*Math.random()),r);//從零開始一直到r-l的r-l+1個數(shù)
int []help=partion(arr,l,r);
QuickSort(arr,l,help[0]-1);//小錯
QuickSort(arr,help[1]+1,r);
}
public static void swap(int []arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void main(String[] args) {
int []a={1,2,3,1};
QuickSort(a,0,a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
5.這里分析一下其復雜度
- 時間復雜度
1.最好的情況是每次都從中間劃分，就正如之前說過的二分歸并排序。
T（N）=O(nlog(n))
2.最不好的情況就如我們之前優(yōu)化分析的情況，每次都是最后一個進行劃分的標準數(shù)比前面的數(shù)都大
也就是 T(N)=T(n+n-1+...+2+1)=T(1/2n*(n-1))=O(n^2)
而通常情況，由于涉及概率問題 不再深究有興趣的盆友可以看看這位老哥的帖子 -
空間復雜度見圖
字丑勿怪2333
-
堆排序
- 堆結構
- 在說堆排的時候我們先了解一下堆這種結構吧堆其實是就是數(shù)組。只是我們把數(shù)組腦補成一個完全二叉樹。
2.完全二叉樹包括滿二叉樹。
3.根節(jié)點為n的話，子節(jié)點為2*n+1
- 大小根堆：根節(jié)點都比子節(jié)點大的為大根堆
怎么把數(shù)組生成大根堆
想法是這樣的
從最開始的跟位置不斷和上一根結點比較如果比根節(jié)點大就交換指針放到根節(jié)點位置不斷循環(huán)直到 堆的頂部
代碼如下：
package paixu;
public class Heap_Big_Initialise {
public static void HeapIntialise(int[]arr){
for (int i = 0; i < arr.length; i++) {
HeapInsert(arr,i);
}
}
public static void HeapInsert(int[] arr,int i){
while (arr[i]>arr[(i-1)/2]){
swap(arr,i,(i-1)/2);
i=(i-1)/2;
}
}
public static void swap(int[]arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void main(String[] args) {
int arr[]={1,2,3,5,4};
HeapIntialise(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
那怎么通過堆結構進行排序呢？
這就引入了heapify的概念了，即使刪除堆頂元素的堆再次成為堆。
首先小根堆堆頂元素是一定為最小的,我們用一個數(shù)組不斷得保留堆頂元素的值，然后把最底下的一個葉子結點放在堆頂，讓它不斷地向下和比它小的子節(jié)點交換。
代碼如下
package paixu;
public class heap {
public static void heapsort(int[]arr){
//建堆
for (int i = 0; i < arr.length; i++) {
heapinsert(arr,i);
}
int size=arr.length-1;
while (size>0) {
swap(arr, 0, size--);
heapfy(arr, size);
}
}
//建大根堆用
public static void heapinsert(int[] arr,int i){
while (arr[i]>arr[(i-1)/2]){
swap(arr,i,(i-1)/2);
i=(i-1)/2;
}
}
//從上往下不斷比較的方法
public static void heapfy(int []arr,int size){
int index=0;
int left=index*2+1;
while(left<size){
int large=(arr[left]>arr[left+1])&&left+1<=size?left:left+1;
large=arr[index]>arr[large]?index:large;
if(index==large){
break;
}
swap(arr,large,index);
index=large;
left=index*2+1;
}
}
//交換函數(shù)
public static void swap(int[]arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void main(String[] args) {
int arr[]={1,3,2,6};
heapsort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
-
要知道在建堆的時候會進行交換。
就如下圖
image.png
所以堆排序是不穩(wěn)定的
P.S.
對于二分歸并排序我只要保證歸并的時候左邊小于等于右邊就先把左邊歸并，就可以保證二分歸并排序的穩(wěn)定性。
對于快排，是可以實現(xiàn)穩(wěn)定排序的但是已經是論文級別的難度了，這里不說了。
關于工程排序算法
IMG_0219(20190408-164936).jpg
桶排序
個人感覺桶排序是最笨拙也是最有靈魂的排序了
1.它是不基于比較的排序，時間復雜度可達到O（n）
2.它的基本想法是，比如說我對1~6六個數(shù)進行進行排序，我就申請六個數(shù)的輔助數(shù)組。然后待比較元素和數(shù)組下標一致的話該下標下的計數(shù)器++，
然后我按計數(shù)器個數(shù)一次輸出輔助數(shù)組下表就好了。
3.當然這樣會有數(shù)據(jù)范圍與數(shù)據(jù)量的問題，數(shù)據(jù)量很大的話我就只對你數(shù)據(jù)的前幾位進行桶排序，然后再對每個桶里的數(shù)據(jù)的前幾位排序進行桶排序，可見這并不具有普適性。
4.但桶排序這種思想有時候能做很取巧的事。
- 關于桶排序思想的運用
給定一個數(shù)組，求如果排序之后，相鄰兩數(shù)的最大差值，要求時
間復雜度O(N)，且要求不能用非基于比較的排序
這個方法很精妙
1.給我n個數(shù)我就準備n+1個桶，通過遍歷我得到最大值和最小值，計算最大值最小值的差值，把這個插值分成n份，標記到從1號桶到n號桶上，0號桶上放置最小值，n號桶上放置最大值。
2.然后我遍歷待排序數(shù)組，把每個數(shù)組都與最小值相減，用這個差值去除之前分得每個桶每份的差值，得到要放入桶的序號，然后判斷該桶內最大值和最小值和剛放進去的這個數(shù)的關系，刷新。這樣我只要用一個全局變量MAX記錄相鄰最大值和后一個桶的最小值的插值之中最大的那個就好了。
那么問題來了
我為什么要有把差值分成n份呢即我為何要準備n+1個桶呢，重點來了由于鴿巢原理 必有一個桶是空的 這就保證了我的max是不可能在一個桶里的兩個數(shù)的差值取到的。而只可能是兩個及以上（中間有空桶）的桶之間取到的
具體關于n分的詳細分析
代碼
package basic_class_01;
import java.util.Arrays;
public class 桶排序 {
public static int maxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int len = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
if (min == max) {
return 0;
}
boolean[] hasNum = new boolean[len + 1];
int[] maxs = new int[len + 1];
int[] mins = new int[len + 1];
int bid = 0;
for (int i = 0; i < len; i++) {
bid = bucket(nums[i], len, min, max);
mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
hasNum[bid] = true;
}
int res = 0;
int lastMax = maxs[0];
int i = 1;
for (; i <= len; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - lastMax);
lastMax = maxs[i];
}
}
return res;
}
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
// for test
public static int comparator(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
Arrays.sort(nums);
int gap = Integer.MIN_VALUE;
for (int i = 1; i < nums.length; i++) {
gap = Math.max(nums[i] - nums[i - 1], gap);
}
return gap;
}
public static void main(String[] args) {
int []a={1,4};
System.out.println(maxGap(a));
}
}
