算法就是这么一回事（排序）（第一部分）

浏览数：23 / 时间：2015年06月08日

一、概述　

　　排序有好几种方法，可以通过插入、交换、选择、合并等一些方式来让一些数据按照我们期望的方式显示，让我们可以更加清楚明白我们所需要的信息。

举个例子，操作系统的文件浏览器可以按照各种方式显示我们的文件，常见的windows系统中可以通过

我们可以寻找自己最近修改的文档（按照时间降序），也可以按照名字字母来排序。也可以按照文件类型来找，也可以通过按照时间来排序。这些简单的功能可以给我们提供了很多功能，计算机也就是有了中断等简单功能造就了强大的选择能力。

二、排序的种类

　　按照维基百科上的介绍，可以分为稳定的、不稳定的、不实用的（稳定不稳定是通过数学公式来计算的，稳定的代表就像冒泡算法一样，对数据没有任何期望，不稳定算法就比较差了，最坏和最好差的好多）。

　　这次我们只做以下几种算法分析（皆不需要额为空间）

　　稳定的：冒泡排序、插入排序、基数排序。

　　不稳定的：选择排序、希尔排序、快速排序、堆排序。

说明：虽然完全逆序的情况下，快速排序会降到选择排序的速度，不过从概率角度来说（参考信息学理论，和概率学），不对算法做编程上优化时，快速排序的平均速度比堆排序要快一些。这也就是C#也以快速排序为默认排序方式。

三、冒泡排序

　　冒泡排序的逻辑关系在于，以每次循环（最外层）都会找到一个除了上一个循环找到的的最大或最小值的次最大最小值（这里的次代表次于上一个，是相对），因为，每次循环都会拿两个相邻的作比较，符合，ok，不符合，交换，这样就每次大的循环都会有一个最大或最小值被我们一个个通过对比找出来。

　　　直接上图就像气泡在水中会上浮一样。

　　冒泡算法的代码如下：　　

　代码：

 1 #include <iostream>
 2 #include <iterator>
 3 #include <vector>
 4 #include <ctime>
 5 #include <random>
 6 #include <functional>
 7 #include <algorithm>
 8 using namespace std;
 9 int intSwap(int& a,int& b)//交换
10 {
11     int intswaptemp=a;
12     a=b;
13     b=intswaptemp;
14     return 0;
15 }
16 int BullerSort(vector<int> &ivec)
17 {
18     //大的循环，每次循环会找出次最大最小值（第一次当然就是最大值）
19     //假设我们要从小到大
20     for(int i=0;i<ivec.size();i++)
21     {
22         //这里我们定义从首---->>>尾，反之也行，只需要对应修改即可
23         for(int j=0;j<ivec.size()-i;j++)
24         {
25             if(ivec[j]>ivec[j+1])
26                 intSwap(ivec[j],ivec[j+1]);
27         }
28     }
29     return 0;
30 }
31 
32 int main()
33 {
34     clock_t start,end;
35     vector<int> ivec;
36     srand(14);
37     for(int i=0;i<10000;i++)//10k
38         ivec.push_back((int)rand());//这里最好不要这样，应该临时设定一个变量用于保存随机值。防止出现不可预知的问题
39 
40     start=clock();
41     BullerSort(ivec);
42     end=clock();
43     for(int i=0;i<10000;i+=500)
44         cout<<ivec[i]<<‘\t‘;
45     cout<<endl;
46     cout<<"the time is "<<end-start<<endl;
47     return 0;
48 }