目錄
1. 概述
2. 插入排序
2.1 直接插入排序
2.2 希爾排序（縮小增量排序）
3. 選擇排序
3.1 直接選擇排序
3.2 堆排序
4. 交換排序
4.1 冒泡排序
4.2 快速排序
4.2.1. 思想
4.2.2 三種分割方式
4.2.3 快速排序的優化
4.2.4 快速排序的非遞回方式
4.2.5 快速排序的特性總結
5. 歸并排序
6. 計數排序（非比較型別的排序）
1. 概述
排序概念：就是將一串記錄按照其中某個或某些關鍵字的大小，遞增或遞減的排列起來的操作，
穩定性：通俗的將就是資料元素不發生有間隔的交換，例如：
內部排序：資料元素全部放在記憶體中的排序
外部排序：資料元素太多不能一次加載到記憶體中，根據排序程序的要求不能在內外存之間移動資料的排序，
注意：以下的排序默認排升序，默認待排序列為：2，5，1，3，8，6，9，4，7，0，6
2. 插入排序
把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列
2.1 直接插入排序
1. 思想：
對于一個元素，將其與前面元素進行比較，將其插入到合適的位置，
排升序：將待排元素依次與序列中元素從右往左比，若待排元素小，則繼續往前比，找到合適位置插入，原來元素的位置按順序往后搬移，
2. 畫圖說明：
說明：第一個元素默認它有序，所以從第二個元素開始進行比較然后插入，5比2大，繼續下一個，將1依次比較插入2前面，將3依次比較插入5前面，8比5大，不用管，繼續下一個，將6依次比較插在8面，9比8大，不用管，將7依次比較，插在8前面，將0依次比較插在1前面，將6依次比較插在7前面，插入完成，
3.代碼展示：
public class InsertSort {
public static void insertSort(int[] array){
for(int i = 1;i < array.length;i++){ //讓從1下標開始，因為如果只有一個元素，它自己默認有序
int key = array[i]; //從陣列中的第二個元素開始比較，進行插入
int end = i-1; //end的位置是要插入元素的前一個位置
while(end >= 0 && key < array[end]){ //end不能越界，找待插入的位置，此處注意：key不能小于等于array[end]，否則為不穩定
array[end+1] = array[end];
end--;
}
array[end+1] = key; //找到位置進行插入，因為上面end--了，所以這里要插入的位置為end+1
}
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
insertSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}結果：
4.特性總結：
時間復雜度：回圈嵌套，O(N^2)，最優情況：當序列接近有序，插入的元素比較少，為O(N)
空間復雜度：不借助輔助空間，O(1)
穩定性：資料元素不發生有間隔的交換，穩定
應用場景：資料量小，接近有序
2.2 希爾排序（縮小增量排序）
1. 思想：
選一個整數為資料元素的間隔，將間隔相同的資料元素分為一組，分別對這些組進行插入排序，間隔減小，重復上述操作，當間隔減少到1的時候，資料元素即排好序了，
2. 畫圖說明：
說明：gap為間隔，這里依次將gap=4，2，1，先把間隔為4的資料元素用插入排序排好序，再利用插入排序排gap=2 的資料元素，依次重復上述操作，即可，
3. 代碼展示：
public class ShellSort {
public static void shellSort(int[] array){
int gap = array.length;
while(gap > 1){
gap = gap/3+1;
for(int i = gap;i < array.length;i++){ //跟插入排序一樣，都從一組數的第二個元素開始，因為第一個數默認有序
int key = array[i];
int end = i - gap; //end的位置也是代排數的前一個，但這里間隔為gap，所以前一個位置為i-gap
while(end >= 0 && key < array[end]){ //與插入排序保持不變,找待插入的位置
array[end+gap] = array[end]; // key小于前一個數，讓end位置的元素往后移一位，
end -= gap; //end每次向左走的時候一次走gap的間隔
}
array[end+gap] = key; //找到待排位置將key插入相應位置
}
}
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
shellSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}結果：
4. 特性總結：
希爾排序是對直接插入排序的優化，
當gap>1時都是預排序，目的是讓陣列元素接近有序，當gap==1時，陣列已經接近有序了，這樣插入排序將會很快，整體而言，達到了優化的效果，
希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，
gap的取法有多種，最初shell提出取gap=n/2，gap=gap/2，直到gap=1，后來，Kunth提出取gap = [gap/3]+1，在Kunth所著的《計算機程式設計技巧》第3卷中，利用大量的實驗統計資料得出，當n很大時，關鍵碼的平均比較次數和物件平均移動次數大約在n^1.25到1.6n^1.25范圍內，這是利用直接插入排序作為子序列排序方法的情況下得到的，
故時間復雜度暫記為：O(N^1.25)~O(1.6N^1.25)
空間復雜度：沒有借助輔助空間，O(1)
穩定性：資料元素發生了有間隔的交換，不穩定
應用場景：資料比較隨機
3. 選擇排序
每一次從待排資料元素中選出最小（最大）的元素，存放在序列的起始（末尾）位置，直到全部待排序的資料元素全部排完，
3.1 直接選擇排序
1. 思想：
思路1：
找出序列中的最大的元素，若它不在序列的末尾，將它與末尾元素交換位置，依次回圈，
思路2：
每次找元素的時候，找一個最大的和一個最小的，最大的和最后一個交換位置，最小的和第一個交換位置，依次回圈
2. 畫圖說明：
思路1：
說明：先找到序列的最大元素與序列最后一個元素交換，序列的最后的位置朝前移一個，再找新序列的最大元素再與最后一個交換位置，依次回圈，
思路2：
說明：這種方法是一次找兩個元素，跟上面那種本質上一樣，只是一次交換了兩個元素，將最大的與最后一個交換，將最小的與第一個交換
3. 代碼展示：
public class SelectSort {
public static void selectSort1(int[] array){
int size = array.length;
for(int i = 0;i < size-1;i++){ //選擇的趟數，size-1是因為當選擇到序列剩一個元素時就不用選了
int pos = 0; //pos標記最大元素的位置，剛開始是默認為第一個位置
for(int j = 1;j < size-i;j++){ //j=1是因為默認第一個元素的位置為最大元素的位置，所以從第二個元素的位置開始比較
//size-i是因為每趟選擇完后，序列都要減少一個
if(array[j] > array[pos]){
pos = j; //找到最大元素位置，更新pos
}
}
if(pos != size-i-1){ //如果最大元素的位置剛好是最后一個位置，則不需要交換，反之進行交換
swap(array,pos,size-i-1);
}
}
}
public static void selectSort2(int[] array){
int left = 0; //序列的左邊界
int right = array.length-1; //序列的右邊界
while(left < right){ //當序列中至少存在倆元素時
int minPos = left; //剛開始將最小元素的位置設定為序列的第一個位置
int maxPos = left; //剛開始將最大元素的位置也設定為序列的第一個位置
int index = left+1; //從序列的第二個元素開始找最大元素和最小元素的位置
//找最大元素和最小元素的位置
while(index <= right){
if(array[index] < array[minPos]){
minPos = index;
}
if(array[index] > array[maxPos]){
maxPos = index;
}
index++;
}
if(minPos != left){ //當最小的元素不在序列的最左端時交換位置
swap(array,minPos,left);
}
//這里我是先交換最小的元素，但是如果最大的元素在最左側，那么會將maxPos位置的元素更新為最小的元素，導致后面
//交換最大元素的時候maxPos標記的元素不準確，所以下面將maxPos的位置更新了一下
//注意：如果是先交換最大的元素，則更新minPos的位置
if(maxPos == left){
maxPos = minPos;
}
// if(minPos == right){
// minPos = maxPos;
// }
if(maxPos != right){ //當最大元素不在序列的最右端時交換位置
swap(array,maxPos,right);
}
left++; //左邊界+1
right--; //右邊界-1
}
}
public static void swap(int[] array,int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
public static void main(String[] args) {
int[] array = {9,5,1,3,8,6,2,4,7,6,0};
selectSort1(array);
for(int i : array){
System.out.print(i+" ");
}
System.out.println();
selectSort2(array);
for(int i : array){
System.out.print(i+" ");
}
}
}4：特性總結：
時間復雜度：找元素，交換元素是回圈嵌套，O(N^2)
空間復雜度：沒有借助輔助空間，O(1)
穩定性：資料元素存在有間隔的交換，不穩定
缺陷：找最大元素或者最小元素的時候重復比較
3.2 堆排序
1. 思想：
堆排序是利用堆積樹（堆）這種資料結構設計的一種演算法，它是選擇排序的一種，它是通過堆來進行選擇資料，
注意：排升序，建大根堆，排降序，建小根堆，
堆排序分為兩部分：建堆，利用向下調整建堆，再利用堆洗掉的思想排序，
向下調整：
前提：要調整的節點的兩個左右子樹都已滿足堆的特性
方法：建大堆，將根的元素與左右孩子較大的元素交換，建小堆，將根的元素與左右孩子較小的元素交換
堆洗掉思想：
將堆頂元素與最后一個元素交換位置
堆中有效元素減少一個
再對堆頂元素向下調整
2. 畫圖說明：
因為資料元素多，二叉樹的圖看著不太清晰，所以我用以下序列：0，5，3，4，1，2
建堆：
利用堆洗掉思想排序：
3. 代碼展示：
public class HeapSort {
//向下調整
public static void shiftDown(int[] array,int parent,int size){
int child = parent*2+1; //默認將左孩子設為parent的孩子，因為不知道右邊孩子是否存在
while(child<size){
if(child+1<size && array[child+1]>array[child]){ //如果右孩子存在，比較哪個孩子值大
child += 1; //將child設為較大的孩子
}
if(array[parent]<array[child]){ //如果parent小，將parent與child交換
swap(array,parent,child);
parent = child; //更新parent
child = parent*2+1; //更新child
}else{ //如果已經滿足堆特性則直接回傳
return;
}
}
}
//堆排序
public static void heapSort(int[] array){
//建堆
int size = array.length;
int lastLeaf = ((size-1)-1)/2; //找到倒數第一個非葉子節點
for(int root=lastLeaf;root>=0;root--){ //從該結點開始，依次向下調整直到根節點
shiftDown(array,root,size);
}
//利用堆洗掉思想排序,從最后一個元素開始與堆頂元素交換，然后對堆頂元素進行向下調整
int end = size-1;
while(end>0){
swap(array,0,end);
shiftDown(array,0,end);
end--;
}
}
public static void swap(int[] array,int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
heapSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}結果：
4. 特性總結：
時間復雜度：n個元素進行比較，而且太向下調整，調整的深度為完全二叉樹的深度，故時間復雜度為：O(NlogN),logN是log以2為底的N
空間復雜度：沒有借助輔助空間，O(1)
穩定性：元素發生了有間隔的交換，不穩定
應用場景：求前k個最小或者最大，可以和其他排序結合起來增加效率
4. 交換排序
基本思想就是根據序列中兩個記錄鍵值的比較結果來交換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動
4.1 冒泡排序
1. 思想：
依次將序列元素進行比較，若array[i]>array[i+1],交換兩個元素的位置，直到最后一個元素，從中可以得出，每躺冒泡只能確定一個元素的位置，若序列有n個元素，則需要進行n-1躺冒泡，因為序列最后一個元素的位置不用確定，
從比較的次數可以看出：第一躺比較的次數為n-1，第二躺的比較次數為n-2.....即每趟冒泡比較的次數在遞減，即比較次數是為n-1-i，i為冒泡的趟數，
2. 畫圖說明：
3. 冒泡排序的優化：
從上圖可以看出第10躺冒泡沒有進行，因為序列已經有序，即資料元素不在發生交換，
優化：在每趟進行的開始給一個標記isChage=false，如果該躺冒泡發生了元素交換，將isChange=true，在每趟冒泡完進行判斷，如果是Change==false，即沒有發生交換，說明序列已經有序，即不用在繼續冒泡，直接回傳即可，
4. 代碼展示：
public class BubbleSort {
public static void bubbleSort(int[] array){
int size = array.length;
for(int i = 0;i < size-1;i++){
boolean isChange = false; //為了優化冒泡排序給的標記，當元素不發生交換的時候說明已經有序
for(int j = 0;j < size-1-i;j++){
if(array[j+1] < array[j]){
swap(array,j,j+1);
isChange = true;
}
}
if(isChange == false){ //如果元素不發生交換，直接回傳
return;
}
}
}
public static void swap(int[] array,int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
bubbleSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
結果：
5. 特性總結：
時間復雜度：冒泡的趟數，每趟的比較次數，O(N^2)
空間復雜度：不借助輔助空間，O(1)
穩定性：資料元素雖然發生了交換，但是沒有間隔交換，穩定
4.2 快速排序
4.2.1. 思想
快速排序是Hoare提出的一種二叉樹結構的交換排序方法，
基本思想為：任取待排元素序列中的某個元素作為基準值（這里我們取最右側元素為基準值），按照該基準值將序列劃分為兩個區間，左側比基準值小，右側比基準值大，再分別用快速排序遞回排左區間和右區間，
參考代碼：
public static void quickSort(int[] array,int left,int right){ //左閉右開
if(right-left > 1){ //遞回的回傳條件，區間最少得有兩個元素
int div = partition(array,left,right);
quickSort(array,left,div); //遞回排左側
quickSort(array,div+1,right); //遞回排右側
}
}故只要實作分割方法即可，
4.2.2 三種分割方式
1. Hoare法
思想：在左邊找比基準值大的，右邊找比基準值小的，兩個交換位置，最后將較大一側的第一個元素與基準值交換位置，
畫圖說明：
參考代碼：
//分割區間方法1：hoare：左邊找比基準值大的，右邊找比基準值小的，兩個交換位置,最后再將基準值放到中間的位置
public static int partition1(int[] array,int left,int right){
int key = array[right-1]; //找基準值，以最右側元素為基準值
int begin = left; //在左側找的下標
int end = right-1; //在右側找的下標
while(begin < end){
while(array[begin] <= key && begin < end){ //左側找大的，不能越界
begin++;
}
while(array[end] >= key && end > begin){ //右側找小的，不能越界
end--;
}
if(begin != end){
swap(array,begin,end); //begin與end不在同一位置的時候交換，否則沒有交換的必要
}
}
if(begin != right-1){
swap(array,begin,right-1); //將基準值與begin位置的元素交換，begin或者end都行
}
return end; //將分割的位置回傳，begin與end都可以
}2. 挖坑法
思想：將基準值存入key中，基準值的位置為第一個坑位，在左側找比基準值大的，放到第一個坑位上，此時這個元素的原始位置又形成了一個新的坑位，再從右側找比基準值小的，放到前面的坑位上，依次回圈，即將序列分割為兩部分，
畫圖說明：
參考代碼：
//分割區間方法二：挖坑法：基準值是一個坑位，左側找大的放到基準值的坑位上，此時形成了新的坑位，再在右側找小的放到上一個坑位，依次回圈
public static int partition2(int[] array,int left,int right){
int key = array[right-1]; //取最右側元素為基準值，end的位置形成了第一個坑位
int begin = left;
int end = right-1;
while(begin < end){
while(begin < end && key >= array[begin]){ //在左側找比基準值大的
begin++;
}
if(begin < end){
array[end] = array[begin]; //填end坑位，重新生成begin坑位
}
while(begin < end && key <= array[end]){ //在右側找比基準值小的
end--;
}
if(begin < end){
array[begin] = array[end]; //填begin坑位，重新生成end坑位
}
}
array[begin] = key; //將基準值填充在最后一個坑位
return end;
}3. 前后標記法
思想：給兩個標記cur，pre，pre標記cur的前一個，cur開始標記第一個元素，依次往后走，cur小于區間的右邊界，如果cur小于基準值并且++pre不等于cur交換cur與pre位置的元素，最后交換++pre與基準值位置的元素，
畫圖說明：
參考代碼：
//分割區間方法三：前后標記法
public static int partition3(int[] array,int left,int right){
int key = array[right-1];
int cur = left;
int pre = cur-1;
while(cur < right){
if(array[cur] < key && ++pre != cur){ //當cur位置的元素小于基準值并且++pre！=cur的時候，交換
swap(array,cur,pre);
}
cur++;
}
if(++pre != right-1){ //++pre為與基準值交換的位置，所以當++pre！=right-1的時候，交換基準值的位置
swap(array,pre,right-1);
}
return pre;
}4.2.3 快速排序的優化
快速排序的優化：對基準值的選取進行優化，這樣做是為了選取的基準值盡可能的將區間的左右側分的均勻一點兒，
優化方法：三數取中法取基準值，三數：區間的中間元素，最左側元素，最右側元素，取它們三個的中間值，
參考代碼：
//快排優化：三數取中法來取基準值，左側，右側，中間這三個數的中間值來作為基準值,這里回傳的是基準值下標
public static int getIndexOfMid(int[] array,int left,int right){
int mid = left+((right-left)>>1);
if(array[left] < array[right-1]){ //最右側的下標為right-1
if(array[mid] < array[left]){
return left;
}else if(array[mid] > array[right-1]){
return right-1;
}else{
return mid;
}
}else{
if(array[mid] < array[right-1]){
return right-1;
}else if(array[mid] > array[left]){
return left;
}else{
return mid;
}
}
}具體與之前代碼結合方式，我這里選取一種分割方法來進行優化：
參考代碼：
//分割區間方法三：前后標記法
public static int partition3(int[] array,int left,int right){
int index = getIndexOfMid(array,left,right); //用三數取中法獲得基準值的下標
if(index != right-1){
swap(array,index,right-1); //如果下表不在最右側就交換
}
int key = array[right-1];
int cur = left;
int pre = cur-1;
while(cur < right){
if(array[cur] < key && ++pre != cur){ //當cur位置的元素小于基準值并且++pre！=cur的時候，交換
swap(array,cur,pre);
}
cur++;
}
if(++pre != right-1){ //++pre為與基準值交換的位置，所以當++pre！=right-1的時候，交換基準值的位置
swap(array,pre,right-1);
}
return pre;
}4.2.4 快速排序的非遞回方式
非遞回的快速排序借助堆疊這一資料結構
參考代碼：
//非遞回的快速排序，利用堆疊來保存分割的區間，傳參只需要傳陣列即可
public static void quickSort(int[] array){
Stack<Integer> s = new Stack<>();
s.push(array.length);
s.push(0);
while(!s.empty()){
int left = s.pop();
int right = s.pop();
if(right - left == 0){
continue;
}
int div = partition(array,left,right);
s.push(right);
s.push(div+1);
s.push(div);
s.push(left);
}
}4.2.5 快速排序的特性總結
時間復雜度：有比較，遞回，O(NlogN)
空間復雜度：存在遞回，遞回的深度為完全二叉樹的深度，O(logN)
穩定性：資料元素發生有間隔的交換，不穩定
應用場景：資料凌亂且隨機
5. 歸并排序
1. 思想：
歸并排序是將兩個有序序列進行合并，但是我們拿到是一個陣列，所以得先將陣列遞回均分為兩部分，再將兩部分進行合并，
2. 畫圖說明：
遞回均分：
從下往上合并：
3. 代碼展示：
public class MergeSort {
public static void mergeSort(int[] array,int left,int right,int[] temp){
if(right - left > 1){
int mid = left+((right-left)>>1);
mergeSort(array,left,mid,temp); //遞回均分左側
mergeSort(array,mid,right,temp); //遞回均分右側
mergeData(array,left,mid,right,temp); //合并兩個序列，[left,mid) , [mid,right)
System.arraycopy(temp,left,array,left,right-left); //拷貝到原陣列，源，起始位置，新，起始位置，長度
}
}
public static void mergeData(int[] array,int left,int mid,int right,int[] temp){
//[begin1,end1),[begin2,end2),為兩個合并的區間
int begin1 = left;
int end1 = mid;
int begin2 = mid;
int end2 = right;
int index = left; //輔助陣列的下標
while(begin1 < end1 && begin2 < end2){
if(array[begin1] <= array[begin2]){
temp[index++] = array[begin1++];
}else{
temp[index++] = array[begin2++];
}
}
while(begin1 < end1){
temp[index++] = array[begin1++];
}
while(begin2 < end2){
temp[index++] = array[begin2++];
}
}
//重新包裝一下，便于用戶傳參
public static void mergeSort(int[] array){
int[] temp = new int[array.length];
mergeSort(array,0,array.length,temp);
}
}4. 非遞回的歸并排序
給一個間隔，用間隔來表示區間
參考代碼：
//非遞回的歸并排序
public static void mergeSortNor(int[] array){
int size = array.length;
int[] temp = new int[size];
int gap = 1; //先每兩個元素歸并
while(gap < size){
for(int i = 0;i < size;i+=gap*2){
int left = i;
int mid = i+gap;
int right = mid+gap;
if(mid > size){ //防止mid越界
mid = size;
}
if(right > size){ //防止right越界
right = size;
}
mergeData(array,left,mid,right,temp);
}
System.arraycopy(temp,0,array,0,size);
gap <<= 1;
}
}5. 特性總結：
時間復雜度：O(NlogN)
空間復雜度：借助了輔助空間，為輔助陣列的大小，O(N)
穩定性：資料元素不發生有間隔的交換，穩定
應用場景：適合外部排序
6. 計數排序（非比較型別的排序）
1. 思想：
計數排序又稱鴿巢原理，是對哈希直接定址法的變形應用
步驟：
統計相同元素出現次數
根據統計的結果將序列回收到原來的序列中
2. 畫圖說明：
3. 代碼展示：
public class CountSort {
public static void countSort(int[] array){
//找出陣列的最大值與最小值
int maxNum = array[0];
int minNum = array[0];
for(int i = 1;i < array.length;i++){
if(array[i] > maxNum){
maxNum = array[i];
}
if(array[i] < minNum){
minNum = array[i];
}
}
int range = maxNum - minNum + 1; //序列元素的范圍大小
int[] count = new int[range]; //new一個范圍大小的陣列
for(int i = 0;i < array.length;i++){
count[array[i]-minNum]++; //讀取
}
int index = 0; //存入原陣列的下標
for(int i = 0;i < range;i++){
while(count[i] > 0){
array[index] = i + minNum;
index++;
count[i]--;
}
}
}
}4. 性能總結：
時間復雜度：O(N)
空間復雜度：O(M),M為資料范圍的大小
穩定性：資料元素沒有進行有間隔的交換，穩定
應用場景：資料元素集中在某個范圍
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/390343.html
標籤：其他
下一篇：理解Linux—inode