排序總結——————資料結構

文章目錄

• ​​八中排序方式的對比​​

• ​​資料生成​​
• ​​排序算法​​
• ​​性能比較​​
• ​​運作時間比較(ms)​​
• ​​移動次數比較​​
• ​​交換次數比較​​

八中排序方式的對比

資料生成

我采用随機函數來生成随機資料，将生成的資料儲存在.txt檔案裡

生成的資料大小範圍在内,生成的資料完全是随機的

其中

采用目前時間來作為随機數種子

srand(time(NULL));//随機數種子      

生成的資料将儲存在檔案名為以下的檔案裡

代碼如下

#include<bits/stdc++.h>
using namespace std;
int main()
{
  freopen("1e6.txt","w",stdout);//輸出到檔案 
  int n = 1e6;//資料量的大小 
  srand(time(NULL));//随機數種子 
  for(int i=0;i<n;i++)
    printf("%d ",(abs(rand())+n)%n);
  return 0;
}      

排序算法

将會進行以下幾種排序算法比較，

分别比較它們的

• 運作時間：(ms)
• 交換次數：
• 移動次數：

八中排序算法：

1. 插入排序
2. 折半插入排序
3. 希爾排序
4. 冒泡排序
5. 簡單選擇排序
6. 快速排序
7. 堆排序
8. 歸并排序

性能比較

這些排序算法的性能比較如上圖所示，我們通過時間複雜度可以看出，的算法肯定是最慢的，而堆排序，快速排序，歸并排序的平均時間複雜度是,顯然比其他算法快一些。

我們用這些算法對相同的随機資料進行排序，觀察一下它們的運作時間，移動次數，交換次數，來進行更加直覺的分析。

運作時間比較(ms)

排序算法 資料大小	1e3	1e4	1e5	1e6
InsertSort	1	87	7809	889262
BInsertSort	1	75	6828	838490
ShellSort	1	37	413
BubbleSort	3	1	39693	3890712
QuickSort	1	15	151
SelectSort	1	120	11775	1131986
HeapSort	2	21	564
MergeSort	1	23	184

我們觀察運作時間（機關ms），資料是1e3的時候看不出來大的差别，但是當資料逐漸增多，不同的算法排序所用的時間差别也越來越大！

在資料為1e6的時候，快速排序将1e6的資料排完序僅用了0.1s，而冒泡排序将這些資料排序成功需要花費一個多小時，現在我們做的才僅僅是百萬級别的資料，和普通的算法相比，優秀的算法要比它快三萬倍。

在這個大資料的時代，算法的重要性不言而喻。

移動次數比較

排序算法 資料大小	1e3	1e4	1e5	1e6
InsertSort	251935	24834732	2498350057	249759429861
BInsertSort	251944	24834740	2498350073	249759429905
ShellSort	11041	204402	3532741	52682333
BubbleSort	250945	24824741	2498250074	249758429906
QuickSort	4770	61112	763306	8243154
SelectSort	995	9990	99988	999957
HeapSort	10553	139191	1725178	20549336
MergeSort	19952	267232	3337856	39902848

交換次數比較

排序算法 資料大小	1e3	1e4	1e5	1e6
InsertSort	990	9991	99983	999955
BInsertSort	999	9999	99999	999999
ShellSort	3834	57433	763790	8369173
BubbleSort	250945	24824741	2498250074	249758429906
QuickSort	697	6929	74695	867486
SelectSort	995	9990	99988	999957
HeapSort	10553	139191	1725178	20549336
MergeSort	250945	24824741	2498250074	249758429906