目錄

前言

常見的排序算法實現：

1. 冒泡排序

思路分析：

代碼實現：

2.選擇排序

思路分析：

代碼實現：

3.插入排序

思路分析：

代碼實現：

4.快速排序

思路分析：

代碼實現：

---

前言

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。

生活中各種地方都需要用到排序，所以學好排序算法是非常重要的。

排序分為 內部排序 和 外部排序。

內部排序：數據元素全部放在內存中的排序。
外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。

這部分主要是內部排序。排序講解都以升序為例。
————————————————
版權聲明：本文為CSDN博主「風繼續吹TT」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/Edward_Asia/article/details/121419975

常見的四種排序算法：

1. 冒泡排序

2. 選擇排序

3.插入排序

4.快速排序

常見的排序算法實現：

1. 冒泡排序

思路分析：

1.兩兩相鄰元素比較，大的元素往后移，直到讓最大的元素在最后面

2.當有n個元素時，外循環會進行（n-1）次排序，因為最后剩下一個數，不需要比較

3.當進行第i趟排序時，內循環會進行n-i次比較

代碼實現：

 //冒泡排序public void  BubbleSort( int[] arr){//整體思路：通過每一次循環的比較找到最大值int n=arr.length;//外層排序n-1次for(int i=0;i<n-1;i++){//內層比較n-i-1次for(int j=0;j<n-i-1;j++){if(arr[j]>arr[j+1])//交換相鄰的兩個數組，將大的往后排{int temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}}

2.選擇排序

思路分析：

1.首先，找到數組中最大（小）的那個元素;
2.其次，將它和數組的第一個元素交換位置（如果第一個元素就是最大（小）元素那么它就和自己交換）;
3.再次，在剩下的元素中找到最大（小）的元素，將它與數組的第二個元素交換位置。如此往復，直到將整個數組排序。

總結：這種方法叫做選擇排序，因為它在不斷地選擇剩余元素之中的最大（小）者

代碼實現：

 //選擇排序public void SelectSort ( int[] arr){int n=arr.length;//整體思路；內循環找到最小值的下標，與第一個數交換，重復找小，交換for(int i=0;i<n-1;i++){int minIndex=i;for(int j=i+1;j<n;j++){if(arr[j]<arr[minIndex])//如果此時minIndex索引處的值不是最小的，交換{minIndex=j;}}//交換arr[i]和arr[minIndex]int temp=arr[i];arr[i]=arr[minIndex];arr[minIndex]=temp;}}

3.插入排序

思路分析：

1.對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。
2.為了給要插入的元素騰出空間，我們需要將插入位置之后的已排序元素在都向右移動一位。
3.插入排序所需的時間取決于輸入中元素的初始順序。例如，對一個很大且其中的元素已經有序（或接近有序）的數組
4.進行排序將會比對隨機順序的數組或是逆序數組進行排序要快得多

代碼實現：

 //插入排序public void InsertSort(int[] arr){int n=arr.length;//整體思路：從認為第一個元素有序開始，依次將后面的元素插入到這個有序序列中來，直到整個序列有序為止for(int i=1;i<n;i++)//從第二個元素開始遍歷{int key = arr[i];//當前插入的元素int j = i - 1;while (j >= 0 && arr[j] > key)//將key插入到前面有序數組的合適位置{arr[j + 1] = arr[j];//把arr[j]后移一位j--;//j減1繼續比較，直到找到合適的位置}arr[j + 1] = key;}}

4.快速排序

思路分析：

1.將待排序的序列找一個基準值（通常選最兩邊）

2.采用遞歸的思想，將小于基準值的放在他前面，大于基準值的在他后面

代碼實現：

//快速排序public  static void QuickSort(int[] arr)//對外提供的排序方法，方便用戶調用{QuickSort(arr,0,arr.length-1);}//用遞歸排序對數組進行分區，小于基準點的在左邊，大于基準點的在右邊private static int Partition(int[] arr, int left, int right){int pivot = arr[right];//選擇最右邊為基準點int i = left-1;//初始一個小于元素邊界的變量for(int j=left;j<right;j++){if(arr[j]<=pivot)//如果當前元素小于基準點{i++;//交換arr[i]和arr[j]，將小于基準點的元素放在前面int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}//將基準點放在正確的位置上，既i+1int temp = arr[i+1];arr[i+1] = arr[right];arr[right] = temp;return i+1;//返回基準點的最終位置aaaaaalaakka}
//-------------------------------------------------------------------private  static  void QuickSort(int[] arr,int left,int right)//核心的遞歸排序方法，left表示當前排序的左邊界，right表示用邊界{if(left<right){int pivot=Partition(arr,left,right);QuickSort(arr,left,pivot-1);//對基準點左邊進行遞歸排序QuickSort(arr,pivot+1,right);//對基準點右邊進行遞歸排序}}