八大排序

---

前言

排序，就是重新排列表中的元素，使得表中元素滿足按關鍵字有序的過程。

排序有許多種，常用的八大內部排序為冒泡排序、插入排序、選擇排序、希爾排序、快速排序、歸并排序、基數排序、堆排序

這幾種排序沒有絕對的優劣，每種排序都有他們適用范圍

---

?

一、冒泡排序

冒泡排序每一趟排序可以確定一個元素的最終位置，若一次掃描并沒有元素進行交換，則說明表已有序。

void bubbleSort(ElemType a[], int n){for(int i = 0; i < n - 1; i++){bool flag = false;for(int j = n - 1; j > i; j--){if(a[j] < a[j - 1]){swap(a[j], a[j - 1]);flag = true;}}if(flag == false){return;}} }

冒泡排序的性能分析：空間效率為O(1)，最壞時間復雜度為O()，平均時間復雜度為O()。

二、插入排序

插入排序的基本思想是將一個未排序的表，按照關鍵字大小插入到前面已經排好序的子序列（表）中，直到表中所有元素插入完成。

void insertSort(ElemType a[], int n){int i, j;for(int i = 2; i <= n; i++){if(a[i] < a[i-1]){a[0] = a[i];for(j = i - 1; a[0] < a[j]; --j)a[j+1] = a[j]a[j+1] = a[0];}} }

性能分析，插入排序的空間復雜度為O(1)，時間復雜度為O()

三、希爾排序

希爾排序的基本思想是先將待排序的表分割成若干個特殊子表，每個子表的元素在主表中間隔n個元素，并將間隔量稱為增量，然后對各個子表進行插入排序，當整個表中的元素基本有序，再對全體記錄進行一次插入排序

void shellSort(ElemType a[], int n){for(int dk = n/2; dk >= 1; dk = dk/2){for(int i = dk + 1; i <= n; i++){if(a[i] < a[i - dk]){a[0] = a[i];for(int j = i - dk; j > 0 && a[0] < a[j]; j -= dk){a[j+dk] = a[j];}a[j+dk] = a[0]; }}} }

性能分析：空間復雜度為O(1)，時間復雜度為O()，最壞情況為O()

四、快速排序

快速排序的基本思想是分治，在待排序的表中隨機選取一個元素pivot作為樞紐（基準），經過一次排序后，樞紐左邊的元素均小于樞紐，樞紐右邊的元素均大于樞紐，即樞紐確定其在有序表的最終位置，這樣的一次過程稱為一趟快排，或叫一次劃分。

int partition(ElemType a[], int lo, int hi){int pivot = a[lo];while(lo < hi){while(lo < hi && a[hi] >= pivot) --hi;a[lo] = a[hi];while(lo < hi && a[lo] <= pivot) ++lo;a[hi] = a[lo];}a[lo] = pivot;return lo; } void quickSort(ElemType a[], int lo, int hi){if(lo < hi){int pivot = partition(a, lo, hi);quickSort(a, lo, pivot - 1);quickSort(a, pivot + 1, hi);} }

性能分析：空間效率，快排遞歸需要借助遞歸工作棧來保存每層遞歸的信息，其容量和遞歸的最大深度一致。時間效率，最好情況，快排的最壞情況發生在兩個區域分別包含n-1個元素和0個元素時，這種極大程度的不對稱性若發生在每次遞歸中，即對應的表基本有序或基本逆序，則最壞情況的時間復雜度為。

---

總結

?

總結

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

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