排序总结——————数据结构

た入场券 2022-04-03 09:51 205阅读 0赞

### 文章目录 ###

*  八中排序方式的对比
 *   *  数据生成
     *  排序算法
     *  性能比较
     *  运行时间比较(ms)
     *  移动次数比较
     *  交换次数比较

# 八中排序方式的对比 #

## 数据生成 ##

我采用随机函数来生成随机数据，将生成的数据保存在.txt文件里

生成的数据大小范围在 &ThickSpace; \[ 0 , n \] &ThickSpace; \\; \[0,n\]\\; \[0,n\]内,生成的数据完全是随机的

其中  n = 1 0 3 , 1 0 4 , 1 0 5 , 1 0 6 n = 10^3, 10^4,10^5,10^6 n=103,104,105,106

采用当前时间来作为随机数种子

srand(time(NULL));//随机数种子

生成的数据将保存在文件名为以下的文件里

1 e 3. t x t 1e3.txt 1e3.txt

1 e 4. t x t 1e4.txt 1e4.txt

1 e 5. t x t 1e5.txt 1e5.txt

1 e 6. t x t 1e6.txt 1e6.txt

代码如下

#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.  插入排序 ( I n s e r t S o r t ) (InsertSort) (InsertSort)
2.  折半插入排序 ( B I n s e r t S o r t ) (BInsertSort) (BInsertSort)
3.  希尔排序 ( S h e l l S o r t ) (ShellSort) (ShellSort)
4.  冒泡排序 ( B u b b l e S o r t ) (BubbleSort) (BubbleSort)
5.  简单选择排序 ( S e l e c t S o r t ) (SelectSort) (SelectSort)
6.  快速排序 ( Q u i c k S o r t ) (QuickSort) (QuickSort)
7.  堆排序 ( H e a p S o r t ) (HeapSort) (HeapSort)
8.  归并排序 ( M e r g e S o r t ) (MergeSort) (MergeSort)

## 性能比较 ##

![img][]

这些排序算法的性能比较如上图所示，我们通过时间复杂度可以看出， O ( n 2 ) O(n^2) O(n2)的算法肯定是最慢的，而堆排序，快速排序，归并排序的平均时间复杂度是 O ( n &ThinSpace; l o g &ThinSpace; n ) O(n\\,log\\,n) O(nlogn),显然比其他算法快一些。

我们用这些算法对相同的随机数据进行排序，观察一下它们的运行时间，移动次数，交换次数，来进行更加直观的分析。

## 运行时间比较(ms) ##

<table> 
 <thead> 
  <tr> 
   <th>排序算法 数据大小</th> 
   <th>1e3</th> 
   <th>1e4</th> 
   <th>1e5</th> 
   <th>1e6</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>InsertSort</td> 
   <td>1</td> 
   <td>87</td> 
   <td>7809</td> 
   <td>889262</td> 
  </tr> 
  <tr> 
   <td>BInsertSort</td> 
   <td>1</td> 
   <td>75</td> 
   <td>6828</td> 
   <td>838490</td> 
  </tr> 
  <tr> 
   <td>ShellSort</td> 
   <td>0</td> 
   <td>1</td> 
   <td>37</td> 
   <td>413</td> 
  </tr> 
  <tr> 
   <td>BubbleSort</td> 
   <td>3</td> 
   <td>1</td> 
   <td>39693</td> 
   <td>3890712</td> 
  </tr> 
  <tr> 
   <td>QuickSort</td> 
   <td>0</td> 
   <td>1</td> 
   <td>15</td> 
   <td>151</td> 
  </tr> 
  <tr> 
   <td>SelectSort</td> 
   <td>1</td> 
   <td>120</td> 
   <td>11775</td> 
   <td>1131986</td> 
  </tr> 
  <tr> 
   <td>HeapSort</td> 
   <td>0</td> 
   <td>2</td> 
   <td>21</td> 
   <td>564</td> 
  </tr> 
  <tr> 
   <td>MergeSort</td> 
   <td>0</td> 
   <td>1</td> 
   <td>23</td> 
   <td>184</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70]  
我们观察运行时间（单位ms），数据是1e3的时候看不出来大的差别，但是当数据逐渐增多，不同的算法排序所用的时间差别也越来越大！

在数据为1e6的时候，快速排序将1e6的数据排完序仅用了0.1s，而冒泡排序将这些数据排序成功需要花费一个多小时，现在我们做的才仅仅是百万级别的数据，和普通的算法相比，优秀的算法要比它快三万倍。

在这个大数据的时代，算法的重要性不言而喻。

## 移动次数比较 ##

<table> 
 <thead> 
  <tr> 
   <th>排序算法 数据大小</th> 
   <th>1e3</th> 
   <th>1e4</th> 
   <th>1e5</th> 
   <th>1e6</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>InsertSort</td> 
   <td>251935</td> 
   <td>24834732</td> 
   <td>2498350057</td> 
   <td>249759429861</td> 
  </tr> 
  <tr> 
   <td>BInsertSort</td> 
   <td>251944</td> 
   <td>24834740</td> 
   <td>2498350073</td> 
   <td>249759429905</td> 
  </tr> 
  <tr> 
   <td>ShellSort</td> 
   <td>11041</td> 
   <td>204402</td> 
   <td>3532741</td> 
   <td>52682333</td> 
  </tr> 
  <tr> 
   <td>BubbleSort</td> 
   <td>250945</td> 
   <td>24824741</td> 
   <td>2498250074</td> 
   <td>249758429906</td> 
  </tr> 
  <tr> 
   <td>QuickSort</td> 
   <td>4770</td> 
   <td>61112</td> 
   <td>763306</td> 
   <td>8243154</td> 
  </tr> 
  <tr> 
   <td>SelectSort</td> 
   <td>995</td> 
   <td>9990</td> 
   <td>99988</td> 
   <td>999957</td> 
  </tr> 
  <tr> 
   <td>HeapSort</td> 
   <td>10553</td> 
   <td>139191</td> 
   <td>1725178</td> 
   <td>20549336</td> 
  </tr> 
  <tr> 
   <td>MergeSort</td> 
   <td>19952</td> 
   <td>267232</td> 
   <td>3337856</td> 
   <td>39902848</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70 1]

## 交换次数比较 ##

<table> 
 <thead> 
  <tr> 
   <th>排序算法 数据大小</th> 
   <th>1e3</th> 
   <th>1e4</th> 
   <th>1e5</th> 
   <th>1e6</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>InsertSort</td> 
   <td>990</td> 
   <td>9991</td> 
   <td>99983</td> 
   <td>999955</td> 
  </tr> 
  <tr> 
   <td>BInsertSort</td> 
   <td>999</td> 
   <td>9999</td> 
   <td>99999</td> 
   <td>999999</td> 
  </tr> 
  <tr> 
   <td>ShellSort</td> 
   <td>3834</td> 
   <td>57433</td> 
   <td>763790</td> 
   <td>8369173</td> 
  </tr> 
  <tr> 
   <td>BubbleSort</td> 
   <td>250945</td> 
   <td>24824741</td> 
   <td>2498250074</td> 
   <td>249758429906</td> 
  </tr> 
  <tr> 
   <td>QuickSort</td> 
   <td>697</td> 
   <td>6929</td> 
   <td>74695</td> 
   <td>867486</td> 
  </tr> 
  <tr> 
   <td>SelectSort</td> 
   <td>995</td> 
   <td>9990</td> 
   <td>99988</td> 
   <td>999957</td> 
  </tr> 
  <tr> 
   <td>HeapSort</td> 
   <td>10553</td> 
   <td>139191</td> 
   <td>1725178</td> 
   <td>20549336</td> 
  </tr> 
  <tr> 
   <td>MergeSort</td> 
   <td>250945</td> 
   <td>24824741</td> 
   <td>2498250074</td> 
   <td>249758429906</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70 2]

--------------------

本文仅代表个人观点。

[img]: /images/20220403/97d877fa20a3476ebebe73edb8910b94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70]: /images/20220403/1e23e75e2b7e463bace2e42e69b76c0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70 1]: /images/20220403/d74bf002ffb24e8e987900b65d39c2f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70 2]: /images/20220403/223b6f2ede8044bb9da37bcff089e777.png