冒泡排序
時間復(fù)雜度O(n^2)
public static void bubbleSort(int[] arr){
int temp=0;
boolean flag=false;
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1])
{
flag=true;
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
if(!flag)
return;
else
flag=false;
}
}
選擇排序
時間復(fù)雜度O(n^2)
public static void selectSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
int minIndex=i;
int min=arr[i];
for(int j=i+1;j<arr.length;j++){
if(min>arr[j]){
min=arr[j];
minIndex=j;
}
}
if(minIndex!=i){
arr[minIndex]=arr[i];
arr[i]=min;
}
}
}
冒泡排序與選擇排序的區(qū)別
冒泡排序是將“最大值”不斷移向最后杀怠，比如第一次遍歷搂捧，將全部數(shù)的最大值移到最后一個位置，第二次遍歷淳地，將從開始到倒數(shù)第二個數(shù)中的最大值移到倒數(shù)第二個位置，以此類推。過程中可能存在多次交換
選擇排序是首先將第一個數(shù)到最后中的最小值與第一個數(shù)交換额获，然后從第二個數(shù)開始，一直到最后恭应，找出最小值抄邀，與第二個數(shù)交換，以此類推昼榛。在一次遍歷中有且只交換一次
插入排序
時間復(fù)雜度O(n^2)
public static void insertSort(int[] arr){
for(int i=1;i<arr.length;i++){
int insertVal=arr[i];
int insertIndex=i-1;
while(insertIndex>=0&&insertVal<arr[insertIndex]){
arr[insertIndex+1]=arr[insertIndex];
insertIndex--;
}if(insertIndex+1!=i){
arr[insertIndex+1]=insertVal;
}
}
}
原理：
希爾排序
希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法境肾。希爾排序也是一種插入排序，它是簡單插入排序經(jīng)過改進(jìn)之后的一個更高效的版本胆屿，也稱為縮小增量排序奥喻，同時該算法是沖破O(n2）的第一批算法之一
希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序莺掠；隨著增量逐漸減少衫嵌，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時彻秆，整個文件恰被分成一組楔绞，算法便終止。
希爾排序的時間復(fù)雜度比較模糊唇兑，它取決于增量酒朵，大概范圍是O(n^(1.3-2))，但是可以肯定的是希爾排序比直接插入排序要更有效率
public static void shellSort(int[] arr){
int temp=0;
int count=0;
for(int gap=arr.length/2;gap>0;gap/=2){
for(int i=gap;i<arr.length;i++)
for(int j=i-gap;j>=0;j-=gap)
if(arr[j]>arr[j+gap]){
temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}
}
}
希爾排序的原理很好理解扎附，但是代碼需要思考一下：
for(int gap=arr.length/2;gap>0;gap/=2){
for(int i=gap;i<arr.length;i++)
for(int j=i-gap;j>=0;j-=gap)
if(arr[j]>arr[j+gap]){
temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}
}
關(guān)于這里蔫耽，最外層循環(huán)是增量，中間層的 i 從gap開始，即從第一個分組的第二個元素開始匙铡，也就是說跳過所有分組的第一個元素图甜，以便接下來進(jìn)行判斷，交換位置
最里層 j 從 i-gap開始鳖眼，也就是從 i 所在分組的前一個元素開始判斷黑毅，j 遞減gap，一直到0钦讳，也就是將 arr[i]移到所在分組的排序后的位置
矿瘦，也就是之前的插入排序
i 一直遍歷到arr.length，從而將所有分組的所有元素（從第二個開始）都在所在分組進(jìn)行了插入排序
最后隨著gap折減到0愿卒，排序完成
快速排序
快速排序(Quicksort)是對冒泡排序的一種改進(jìn)缚去。基本思想是:通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分琼开，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小易结，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行稠通，以此達(dá)到整個數(shù)據(jù)變成有序序列
快速排序的平均時間復(fù)雜度是O(nlogn)衬衬，最壞情況是O(n^2)
public static void main(String[] args) {
int[] arr=new int[]{9,8,7,6,5,4,3,2,1,0};
quickSort(arr,0,arr.length-1);
for(int e:arr)
System.out.print(e);
}
public static void quickSort(int[] arr,int left,int right){
if(arr==null||arr.length==0)
return;
if(left>right)
return;
int key=arr[left];
int l=left;
int r=right;
int temp=0;
while(l!=r){
while(arr[r]>=key&&l<r)
r--;
while(arr[l]<=key&&l<r)
l++;
if(l<r){
temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
}
}
arr[left]=arr[r];
arr[l]=key;
quickSort(arr,left,l-1);
quickSort(arr,l+1,right);
}
歸并排序
歸并排序(MERGE-SORT)是利用歸并的思想實現(xiàn)的排序方法，該算法采用經(jīng)典的分治(divide-and-conquer)策略（分治法將問題分(divide)成一些小的問題然后遞歸求解改橘，而治(conquer)的階段則將分的階段得到的各答案"修補(bǔ)"在一起滋尉，即分而治之)。
歸并排序的時間復(fù)雜度是O(nlogn)
public class MergeSort {
public static void main(String[] args) {
int[] arr=new int[]{9,8,7,6,5,4,3,2,1,0};
int[] temp=new int[arr.length];
mergeSort(arr,0,arr.length-1,temp);
for(int e:arr)
System.out.print(e);
}
public static void mergeSort(int[]arr,int left,int right,int[]temp){
if(left<right){
int mid=(left+right)/2;
mergeSort(arr,left,mid,temp);
mergeSort(arr,mid+1,right,temp);
merge(arr,left,mid,right,temp);
}
}
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i=left;
int j=mid+1;
int t=0;
while(i<=mid&&j<=right){
if(arr[i]<=arr[j])
temp[t++]=arr[i++];
else
temp[t++]=arr[j++];
}
while(i<=mid)
temp[t++]=arr[i++];
while(j<=right)
temp[t++]=arr[j++];
t=0;
int tempLeft=left;
while(tempLeft<=right)
arr[tempLeft++]=temp[t++];
}
}
基數(shù)排序
基數(shù)排序(桶排序)介紹:
1)基數(shù)排序(radix sort)屬于"分配式排序"(distribution sort)飞主，又稱"桶子法”(bucket sort)或bin sort狮惜、顧名思義，它是通過鍵值的各個位的值,將要排序的元素分配至某些“桶"中達(dá)到排序的作用
2)基數(shù)排序法是屬于穩(wěn)定性的排序碌识，基數(shù)排序法的是效率高的穩(wěn)定性排序法碾篡，穩(wěn)定性排序指:如一個數(shù)組原來為3,1,4,1排序后為1,1,3,4，紅色的1仍然在前面筏餐。
3)基數(shù)排序(Radix Sort)是桶排序的擴(kuò)展
4)基數(shù)排序是1887年赫爾曼·何樂禮發(fā)明的开泽。它是這樣實現(xiàn)的:將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較
5）基數(shù)排序法的時間復(fù)雜度為O (nlog(r)m)魁瞪，其中r為所采取的基數(shù)穆律，而m為堆數(shù)
基數(shù)排序基本思想
將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長度．?dāng)?shù)位較短的數(shù)前面補(bǔ)零。然后导俘，從最低位開始峦耘，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后,數(shù)列就變成一個有序序列旅薄。
例如：將數(shù)組{53,3,542,748,14,214}使用基數(shù)排序,進(jìn)行升序排序
public static void radixSort(int[] arr){
int max=arr[0];
for(int i=0;i<arr.length;i++){
max=max>arr[i]?max:arr[i];
}
int maxLength=(max+"").length();//數(shù)字最大位數(shù)
int[][] bucket=new int[10][arr.length];//十個桶子辅髓，每個深為arr.length
int[] bucketElementCounts=new int[10];//用于記錄每個桶子里面存放了幾個數(shù)據(jù)，便于取出
for(int i=0,n=1;i<maxLength;i++,n*=10){//次數(shù)為數(shù)字最大位數(shù)的循環(huán)
for(int j=0;j<arr.length;j++)//依次放入桶子
{
int digitOfElement=arr[j]/n%10;
bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
bucketElementCounts[digitOfElement]++;
}
int index=0;
for(int k=0;k<10;k++){//依次取出
if(bucketElementCounts[k]!=0){
for(int m=0;m<bucketElementCounts[k];m++)
arr[index++]=bucket[k][m];
}
bucketElementCounts[k]=0;//記得將桶子中存放個數(shù)清零
}
}
}
堆排序
堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，是一種選擇排序洛口，它的最壞矫付，最好．平均時間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序（不能保證相同的兩個數(shù)的位置和原來一樣)
堆是具有以下性質(zhì)的完全二叉樹(葉子節(jié)點只出現(xiàn)在最后一層或倒數(shù)第二層)∶
每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值绍弟，稱為大頂堆
（注意:沒有要求結(jié)點的左孩子的值和右孩子的值的大小關(guān)系）-
每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值,稱為小頂堆
一般升序采用大頂堆骤坐，降序用小頂堆
堆排序的基本思想是:
- 將待排序序列構(gòu)造成一個大頂堆
- 此時轧苫，整個序列的最大值就是堆頂?shù)母?jié)點
- 將其與末尾元素進(jìn)行交換,此時末尾就為最大值
- 然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值姿骏。如此反復(fù)執(zhí)行,便能得到一個有序序列了
public static void heapSort(int[] arr){
int temp=0;
for(int i=arr.length/2-1;i>=0;i--)
adjustHeap(arr,i,arr.length);
for(int j=arr.length-1;j>0;j--){
temp=arr[j];
arr[j]=arr[0];
arr[0]=temp;
adjustHeap(arr,0,j);
}
}
/**
*
* @param arr 待調(diào)整數(shù)組
* @param i 非葉子節(jié)點在數(shù)組中的索引
* @param length 表示對多少個元素進(jìn)行調(diào)整身笤，是遞減的
*/
public static void adjustHeap(int[] arr,int i,int length){
int temp=arr[i];
for(int k=i*2+1;k<length;k=k*2+1){
if(k+1<length&&arr[k]<arr[k+1])
k++;
if(arr[k]>temp)
{
arr[i]=arr[k];
arr[k]=temp;
i=k;
}else
break;
}
}
https://www.cnblogs.com/coding-996/p/12275710.html
https://www.cnblogs.com/chengxiao/p/6104371.html
