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

编程问答

数据结构——排序算法(含动态图片)

發(fā)布時間：2024/2/28 编程问答 24 豆豆

生活随笔收集整理的這篇文章主要介紹了数据结构——排序算法(含动态图片) 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

前言

排序是《數(shù)據(jù)結構》中最基本的學習內(nèi)容。排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序。而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。知識框架如下：

插入排序

插入排序是一種簡單直觀的排序方法，其基本思想在于每次將一個待排序記錄，按其關鍵字大小插入到前面已經(jīng)排好序的子序列中，直到全部記錄插入完成。

直接插入排序

直接插入排序把要排序的序列分成兩部分：第一部分是有序子序列，而第二部分是無序序列。每次挑選無序序列中的第一個元素與第一部分的有序子序列從后往前逐個比較，當待排元素大于子序列中的元素時，將其插入到該元素的后方。直接插入排序會使用一個 "哨兵"，用于存放元素。直接插入排序每次插入一個元素，所以排序趟數(shù)固定為 n-1。

空間復雜度：O(1) ???時間復雜度：O(n^2) ???穩(wěn)定性：穩(wěn)定

#include <stdio.h>void Insertsort(int a[], int low, int high) {int i, j;int temp;for(i = low+1; i <= high; i++){temp = a[i];for(j = i-1; (j >= low)&&(a[j] > temp); j--)a[j+1] = a[j];a[j+1] = temp;} }int main(int argc, char *argv[]) {int i,a[10];printf("輸入10個數(shù)：");for(i = 0; i < 10; i++)scanf("%d", &a[i]);insertsort(a, 0, 9);printf("排序結果是：");for(i = 0; i < 10; i++)printf("%d ", a[i]);printf("\n");return 0; }

折半插入排序

折半插入排序僅僅是減少了比較元素的次數(shù)，約為 O(nlogn)，該比較次數(shù)與待排序列的初始狀態(tài)無關，僅取決于序列中的元素個數(shù)n；而元素的移動次數(shù)沒有改變，它依賴于待排序列的初始狀態(tài)。因此，折半插入排序的時間復雜度仍是 O(n^2)。

空間復雜度：O(1)? ? ?時間復雜度：O(n^2)? ? ?穩(wěn)定性：穩(wěn)定

#include <stdio.h>void BinaryInsertSort(int *arry, int n) {int i, j;int high, low, mid;int temp;for(i = 2; i < n; i++){arry[0] = arry[i];low = 1;high = i-1;while (low <= high){mid = (low+high)/2;if (arry[mid] > arry[0])high = mid-1;else if (arry[mid] <= arry[0])low = mid+1;}for(j = i-1; j >= low; j--){arry[j+1] = arry[j];}arry[low] = arry[0];} }int main(int argc, char *argv[]) {int a[] = {0,2,45,7,8,45,3,6,0};int iLen =sizeof(a)/sizeof(a[0]);for(int i = 1; i < iLen; i++)printf("%d ", a[i]);printf("\n");BinaryInsertSort(a, iLen);for(int i = 1; i < iLen; i++)printf("%d ", a[i]);printf("\n");return 0; }

希爾排序

希爾排序是插入排序的一種又稱 "縮小增量排序"，是直接插入排序算法的一種更高效的改進版本。基本思想:先取一個小于 n 的整數(shù) d1 作為第一個增量，把文件的全部記錄分組。所有距離為 d1 的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序；然后，取第二個增量 d2<d1 重復上述的分組和排序，直至所取的增量??= 1(<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。

空間復雜度：O(1)? ? ?時間復雜度：O(n^2)? ? ?穩(wěn)定性：不穩(wěn)定

#include <stdio.h>void ShellInsertSort(int *arry, int n, int d) {int i,j;for(i = d+1; i < n; i++){if (arry[i-d] > arry[i]){arry[0] = arry[i];for(j = i-d; j > 0 && arry[0] < arry[j]; j = j-d){arry[j+d] = arry[j];}arry[j+d] = arry[0];}} }void ShellSort(int *arry, int n, int d) {int i;for(i = d; i > 0; i--)ShellInsertSort(arry, n, i); }int main(int argc, char *argv[]) {int a[] = {0,2,4,7,8,1,3,6,0};int iLen = sizeof(a)/sizeof(a[0]);for(int i = 1; i < iLen; i++)printf("%d ", a[i]);printf("\n");ShellSort(a, iLen, 4);for(int i = 1; i < iLen; i++)printf("%d ", a[i]);printf("\n");return 0; }

交換排序

交換排序就是根據(jù)序列中兩個元素關鍵字的比較結果來對換這兩個記錄在序列中的位置。常用的交換排序算法有冒泡和快排。交換類的排序，其趟數(shù)和原始序列狀態(tài)有關。

冒泡排序

冒泡排序算法的基本思想是：假設待排序列長為 n，從前往后比較相鄰元素的值，若為逆序，則交換它們，直到序列比較完。每趟冒泡至少把序列中的一個元素放到序列的最終位置，且最多做 n-1 趟冒泡就可以把所有元素排好序。注意：冒泡排序中所產(chǎn)生的有序子序列一定是全局有序(不同于直接插入排序)，也就是說有序子序列中的所有元素的關鍵字一定小于或大于無序序列中所有元素的關鍵字，這樣每一趟排序都會將一個元素放置到其最終的位置上。

空間復雜度：O(1)? ? ?時間復雜度：O(n^2)? ? ?穩(wěn)定性：穩(wěn)定

#include <stdio.h> void bubblesort1(int *arry, int n) {int i, j, k;int temp, flag;for(i = 0; i < n; i++){ flag = 0;for(j = 0; j < n-i-1; j++){if(arry[j] > arry[j+1]){temp = arry[j];arry[j] = arry[j+1];arry[j+1] = temp;flag = 1;}}if(flag == 0) break;} }void bubblesort2(int a[], int n) //雙向冒泡排序 {int low = 0,high = n-1;int i, t, flag = 1;while (low < high && flag){flag = 0;for(i = low;i < high; i++){if (a[i] > a[i+1]){t = a[i];a[i] = a[i+1];a[i+1] = t; flag = 1;}}high--;for(i = high;i > low; i--){if (a[i] < a[i-1]){t = a[i-1];a[i-1] = a[i];a[i] = t;flag = 1;}}low++;} }int main(int argc, char *argv[]) {int a[10]={5,4,8,7,9,5,4,6,3,2};int i;for(i=0;i<10;i++)printf("%d ",a[i]);bubblesort1(a,10);printf("\n");for(i=0;i<10;i++)printf("%d ",a[i]);printf("\n");return 0; }

快速排序

快排算法是基于分治策略的排序算法，其基本思想是，對于輸入的數(shù)組 a[low, high]，按以下三個步驟進行排序。

(1) 分解：以 a[p] 為基準將a[low: high]劃分為三段 a[low：p-1]，a[p] 和 a[p+1：high]，使得 a[low：p-1] 中任何一個元素小于等于 a[p]，?而 a[p+1: high] 中任何一個元素大于等于 a[p]。

(2) 遞歸求解：通過遞歸調(diào)用快速排序算法分別對 a[low：p-1] 和 a[p+1：high] 進行排序。

(3) 合并：由于對 a[low：p-1] 和 a[p+1：high] 的排序是就地進行的，所以在 a[low：p-1] 和 a[p+1：high] 都已排好序后，不需要執(zhí)行任何計算，a[low：high] 就已經(jīng)排好序了。

想要更詳細的了解快排，可以看這篇文章：快速排序的4種優(yōu)化

空間復雜度：O(logn)? ? ?時間復雜度：O(nlogn)? ? ?穩(wěn)定性：不穩(wěn)定

快排動圖(網(wǎng)上找的動圖，其中有一個基準為 6?的標識錯誤。雖然基準選擇方法不一樣，但排序過程還是一樣的)：

#include <stdio.h>int Partition(int a[], int low, int high) {int i,j,k,temp;i = low; j = high+1;k = a[low];while(1){while(a[++i] < k && i < j);while(a[--j] > k);if(i >= j) break;else{temp = a[i];a[i] = a[j];a[j] = temp;}}a[low] = a[j];a[j] = k;return j; }void QuickSort(int a[], int low, int high) {if(low < high){int q = Partition(a, low, high);QuickSort(a, low, q-1);QuickSort(a, q+1, high);} }int main(int argc, char *argv[]) {int i;int a[10] = {3,4,5,6,1,2,0,7,8,9};QuickSort(a, 0, 9);for(i = 0; i < 10; ++i)printf("[%d]", a[i]);printf("\n");return 0; }

選擇排序

選擇排序是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。選擇排序是不穩(wěn)定的排序方法。

簡單選擇排序

空間復雜度：O(1)? ? ?時間復雜度：O(n^2)? ? ?穩(wěn)定性：不穩(wěn)定

#include <stdio.h> void selectionsort(int a[], int n) {int i,j,k,t;for(i = 0; i < n-1; i++){k = i;for(j=i+1;j<n;j++){if(a[j] < a[k])k = j;}if(k != i){t = a[i];a[i] = a[k];a[k] = t;}} }int main(int argc, char *argv[]) {int i, a[10];for(i = 0; i < 10; i++)scanf("%d", &a[i]);selectionsort(a, 10);for(i = 0; i < 10; i++)printf("%d ", a[i]);printf("\n");return 0; }

堆排序

堆排序是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法。分為兩種方法：大頂堆：每個節(jié)點的值都大于或等于其子節(jié)點的值，在堆排序算法中用于升序排列；小頂堆：每個節(jié)點的值都小于或等于其子節(jié)點的值，在堆排序算法中用于降序排列；

想要更詳細的了解堆，可以看這篇文章：通俗易懂的講解堆排序(含Gif圖)

空間復雜度：O(1)? ? ?時間復雜度：O(nlogn)? ? ?穩(wěn)定性：不穩(wěn)定

#include <stdio.h> #include <math.h>void heap_ajust_min(int *b, int i, int size) //a為數(shù)組，size為堆的大小 {int lchild = 2*i; //i的左孩子節(jié)點序號 int rchild = 2*i +1; //i的右孩子節(jié)點序號 int min = i; //記錄根和左右子樹中最小的數(shù)的下標int temp;if(i <= size/2) //調(diào)整不需要從葉結點開始{if(lchild<=size && b[lchild]<b[min]){min = lchild;} if(rchild<=size && b[rchild]<b[min]){min = rchild;} //兩個if語句尋找三個結點中最小的數(shù)if(min != i) //如果min不等于i，說明最小的值在左右子樹中{temp = b[i]; //交換a[i]和a[min]的值b[i] = b[min];b[min] = temp;heap_ajust_min(b, min, size); //被交換的子樹可能不滿足堆的定義，需要對被交換的子樹重新調(diào)整}} }void build_heap_min(int *b, int size) //建立小根堆 {int i;for(i = size/2; i >= 1; i--){ //非葉子節(jié)點最大序號值為size/2，從這個結點開始調(diào)整 heap_ajust_min(b, i, size); //注意for中的循環(huán)條件(i = size/2; i >= 1; i--) } }void heap_sort_min(int *a, int size) {int i;int temp;for(i = size; i >= 1; i--){temp = a[1];a[1] = a[i];a[i] = temp; //交換堆頂和最后一個元素heap_ajust_min(a, 1, i-1); //再一次調(diào)整堆頂節(jié)點成為小頂堆} } int main(int argc, char *argv[]) {int a[] = {0,5,8,45,9,36,35,22,46,37,10,79,100,63,12,18,77,88,50,99,95};int size = sizeof(a)/sizeof(int) -1;int i,j;int count = 1;build_heap_min(a, size);printf("小頂堆:\n"); for(i = 0; i <= 4; i++){for(j = 0; j < pow(2,i); j++){if(count <= size){printf("%d ", a[count++]);}else{break;}}printf("\n");}printf("\n");heap_sort_min(a, size);printf("堆排序之后的序列為：\n");for(i = 1; i <= size; i++)printf("%d ", a[i]);printf("\n");return 0; }

歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。歸并排序是一種穩(wěn)定的排序方法。注意：一般而言，對于 N 個元素進行 k-路 歸并排序時，排序的趟數(shù) m 滿足 k^m = N，從而 m = logk(N)向上取整。

空間復雜度：O(n)? ? ?時間復雜度：O(nlogn)? ? ?穩(wěn)定性：穩(wěn)定

#include <iostream> using namespace std; int *temp;//將兩個非降序序列l(wèi)ow--mid,mid+1--high合并為一個新的非降序序列 void Merge(int a[], int low, int mid, int high) {int len = high - low + 1;int i = low, j = mid+1; //i，j分別為兩個子序列的游標int k = 0; //為新合并序列的游標while(i <= mid && j <= high){if(a[i] <= a[j]){temp[k++] = a[i++];}else{temp[k++] = a[j++];}}while(i <= mid){ //若第一個子序列有剩余，則直接接到尾部temp[k++] = a[i++];}while(j <= high){ //若第二個子序列有剩余，則直接接到尾部temp[k++] = a[j++];}//copy到a[]for(k = 0; k < len; k++)a[low+k] = temp[k]; }//low high為待排序列左右邊界 void MergeSort(int a[], int low, int high) {if(low < high){int mid = (low + high)/2;MergeSort(a, low, mid); //遞歸的劃分左右兩個子序列MergeSort(a, mid+1, high);Merge(a, low, mid, high); //合并} }int main() {int a[10] = {9,8,7,6,5,4,3,2,1,0};temp = new int[10];MergeSort(a, 0, 9);for(int i = 0; i < 10; i++)cout << a[i] <<" ";cout <<endl;delete []temp;return 0; }

常用排序算法復雜度和穩(wěn)定性總結

動態(tài)圖片來源于：

https://blog.csdn.net/qq_42453117/article/details/99680831

https://www.cnblogs.com/fivestudy/p/10064969.html

總結

以上是生活随笔為你收集整理的数据结构——排序算法(含动态图片)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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