排序的概念

• 排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
• 穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
• 內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
• 外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。

常見的排序算法

基本思想

直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。

直接插入排序

比如有手上有很多的牌，第一次抓一張牌出來，放到最前面，認為有序，第二次在抓一張牌出來和有序的牌中作比較，找到合適位置插入，依次類推。

直接插入排序的特性總結(jié)：

元素集合越接近有序，數(shù)據(jù)量比較少，直接插入排序算法的時間效率越高

時間復雜度：O(N^2)

空間復雜度：O(1)，它是一種穩(wěn)定的排序算法

穩(wěn)定性：穩(wěn)定

算法實現(xiàn)

對于 3 2 5 8 4 7 6 9

對于這種情況

不斷重復重復第一次的操作就行，如果當前數(shù)比前一個數(shù)大，外循環(huán)就往后走

//2 4 5 9 3 6 8 7 1 0 for(int i=1;i<size;++i) {int key =array[i];//保存當前數(shù)int end = i-1;while(key < array[end]&& end>=0){array[end+1] = array[end];//往后搬移end--;}array[end+1]=key } void InsertSort(int *array, int size) {for (int i = 1; i < size; ++i){int key = array[i];int end = i - 1; //i前面的已經(jīng)排好序了while (key < array[end] && end >= 0){array[end + 1] = array[end];end--;}array[end + 1] = key;} }

希爾排序

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后，取，重復上述分組和排序的工作。當?shù)竭_=1時，所有記錄在統(tǒng)一組內(nèi)排好序。

希爾排序的特性總結(jié)：

希爾排序是對直接插入排序的優(yōu)化。

當gap > 1時都是預排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。

希爾排序的時間復雜度不好計算，需要進行推導，推導出來平均時間復雜度： O(N1.3—N2）沒有到O(N2)

穩(wěn)定性：不穩(wěn)定‘

void ShellSort(int* array, int size) {int gap = size;while (gap > 1) {gap = gap / 3 + 1;for (int i = gap; i < size; ++i)//i每回加1，讓分組同時進行排序，不需要+gap{int key = array[i];int end = i - gap; //i的前一個元素while (key < array[end] && end >= 0){array[end + gap] = array[end];end -= gap;}array[end + gap] = key;} } }

選擇排序

基本思想：

每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。

直接選擇排序:

在元素集合array[i]--array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素

若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換

在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素

直接選擇排序的特性總結(jié)：

直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用

時間復雜度：O(N^2)

空間復雜度：O(1)

穩(wěn)定性：不穩(wěn)定

代碼實現(xiàn)

void Swap(int *pLeft, int *pRight) {int temp = *pLeft;*pLeft = *pRight;*pRight = temp; } //直接選擇排序 void SelectSort(int*array, int size) {for (int i = 0; i < size - 1; ++i) //總共找多少次,-1是因為最后一次，區(qū)間中只有一個元素了{//找區(qū)間中最大元素的位置//找最大元素的方式int maxPos = 0; //找最大的元素for (int j = 1; j < size - i; ++j) //-i，從沒排序的序列中找最大的元素{if (array[j]>array[maxPos]) //如果大，下標變更maxPos = j;}if (maxPos != size - i - 1) //如果最大元素下標不等于此時當前沒排序區(qū)間的最后一個元素Swap(&array[maxPos], &array[size - i - 1]);//最大位置的元素和最后位置的元素交換} }

直接選擇排序優(yōu)化

一次排序時，找出當前區(qū)間，當前區(qū)間，當前區(qū)間最大和最小的元素，最大元素和當前區(qū)間的最后一個元素交換最小元素和當前區(qū)間第一個元素進行交換，交換完，區(qū)間縮小，重復操作，直到有序

//選擇排序優(yōu)化 void SelectSort_OP(int*array, int size) {int begin = 0;int end = size - 1;while (begin < end){int maxPos = begin;//認為當前區(qū)間第一個元素最大int minPos = begin;//認為當前區(qū)間第一個元素最小int i = begin;//i從當前區(qū)間第一個元素開始//在區(qū)間中找到最大和最小元素的位置while (i <= end){if (array[i]>array[maxPos])maxPos = i;if (array[i] < array[minPos])minPos = i;i++;}//最大和最小元素和當前區(qū)間第一位置和最后一位置進行交換if (maxPos != end)Swap(&array[maxPos], &array[end]);//交換的是下標里的值，下標并沒有改變//如果當前區(qū)間最后的元素放的正好是你找到最小元素,更新最小元素的位置if (minPos == end)minPos = maxPos;if (minPos != 0)Swap(&array[minPos], &array[begin]);//縮小區(qū)間begin++;end--;} }

直接選擇排序的缺陷

每選一次都要從前往后再比一次

堆排序

堆的簡介與相關(guān)實現(xiàn)

堆排序的特性總結(jié)：

堆排序使用堆來選數(shù)，效率就高了很多。

時間復雜度：O(N*logN)

空間復雜度：O(1)

穩(wěn)定性：不穩(wěn)定

代碼實現(xiàn)

//O(logN) void HeapAdjust(int*array, int size, int parent) {int child = parent * 2 + 1; //左孩子//int right = parent * 2 + 2;//右孩子while (child<size){//找左右孩子中最大的if (child+1<size && array[child + 1] > array[child])child += 1;//檢測雙親是否滿足堆的性質(zhì)if (array[child] > array[parent]) //不滿足{Swap(&array[child], &array[parent]);parent = child;child = parent * 2 + 1;}elsereturn;} }//O(NlogN) void HeapSort(int *array, int size) {//建堆----升序(大堆) 降序(小堆)//從倒數(shù)第一個非葉子結(jié)點----向下調(diào)整//size-1數(shù)組中最后一個數(shù)，parent=(child-1)/2；int last = ((size - 1 - 1) / 2);for (; last >= 0; last)HeapAdjust(array, size, last--);//排序---堆的刪除int end = size - 1; //剩余排序的元素個數(shù)while (end){Swap(&array[0], &array[end]);HeapAdjust(array, end, 0);--end;} }

排序下

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的排序上---(排序概念，常见排序算法，直接插入，希尔排序，直接选择排序，堆排序)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。