當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

排序算法有哪些？

發布時間：2025/5/22 编程问答 13 豆豆

生活随笔收集整理的這篇文章主要介紹了排序算法有哪些？小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

1、冒泡排序（Bubble Sort）
1.1 算法描述
·比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
·對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應·該會是最大的數；
·針對所有的元素重復以上的步驟，除了最后一個；
·重復步驟1~3，直到排序完成

1.2總結
內層循環每次結束后都能得到本輪最大的一個數，外層循環控制要比較多少輪
它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端

2、選擇排序（Selection Sort）
工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

3、插入排序（Insertion Sort）
3.1從第一個元素開始，該元素可以認為已經被排序；
3.2取出下一個元素，在已經排序的元素序列中從后向前掃描；
3.3如果該元素（已排序）大于新元素，將該元素移到下一位置；
3.4重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
3.5將新元素插入到該位置后；
3.6重復步驟2~5。

4、希爾排序（Shell Sort）
簡單插入排序很循規蹈矩，不管數組分布是怎么樣的，依然一步一步的對元素進行比較，移動，插入，比如[5,4,3,2,1,0]這種倒序序列，數組末端的0要回到首位置很是費勁，比較和移動元素均需n-1次。
希爾排序是簡單插入排序的改進版。它與插入排序的不同之處在于，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。
希爾排序過程如下：

希爾排序的核心在于間隔序列的設定。既可以提前設定好間隔序列，也可以動態的定義間隔序列。

5、歸并排序（Merge Sort）
歸并排序（MERGE-SORT）是利用歸并的思想實現的排序方法，該算法采用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并

package sortdemo;import java.util.Arrays;/*** Created by chengxiao on 2016/12/8.*/ public class MergeSort {public static void main(String []args){int []arr = {9,8,7,6,5,4,3,2,1};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int []arr){int []temp = new int[arr.length];//在排序前，先建好一個長度等于原數組長度的臨時數組，避免遞歸中頻繁開辟空間sort(arr,0,arr.length-1,temp);}private static void sort(int[] arr,int left,int right,int []temp){if(left<right){//先從小區域先排序再到大區域int mid = (left+right)/2;sort(arr,left,mid,temp);//左邊歸并排序，使得左子序列有序sort(arr,mid+1,right,temp);//右邊歸并排序，使得右子序列有序merge(arr,left,mid,right,temp);//將兩個有序子數組合并操作}}private static void merge(int[] arr,int left,int mid,int right,int[] temp){//left 是左子序列的開始，mid是它的結尾//mid+1是右子序列的開始，right是它的結尾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中temp[t++] = arr[i++];}while(j<=right){//將右序列剩余元素填充進temp中temp[t++] = arr[j++];}t = 0;//將temp中的元素全部拷貝到原數組中while(left <= right){arr[left++] = temp[t++];}} }

6、快速排序（Quick Sort）
從數列中挑出一個元素，稱為 “基準”（pivot）；
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

public class QuickSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 對 arr 進行拷貝，不改變參數內容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);return quickSort(arr, 0, arr.length - 1);}private int[] quickSort(int[] arr, int left, int right) {if (left < right) {//先從大區域先排序再到小區域int partitionIndex = partition(arr, left, right);quickSort(arr, left, partitionIndex - 1);quickSort(arr, partitionIndex + 1, right);}return arr;}private int partition(int[] arr, int left, int right) {// 設定基準值（pivot）int pivot = left;int index = pivot + 1;//index代表的就是比基準值大的那些數的下標最小值//可以把index認為就是大于基準值的數的下標，index前面的都是比基準值小的for (int i = index; i <= right; i++) {if (arr[i] < arr[pivot]) {swap(arr, i, index);index++;}}swap(arr, pivot, index - 1);return index - 1;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}

總結

以上是生活随笔為你收集整理的排序算法有哪些？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。