简单排序(C++)

简单排序(C++)

简单排序

• 数据结构与算法的游戏从简单排序开始
• • 选择排序
  • 冒泡排序
  • 插入排序
  • 希尔排序
  • 简单排序性能PK赛

数据结构与算法的游戏从简单排序开始

  简单排序是排序算法中基础的部分，这部分算法都是属于O(n2)的算法，虽然从数量级上看时间消耗要比后续的O(nlog(n))级别的算法要慢，但实际表现却不见得；特别是优化过后的插入排序，在对基本有序序列的排序的时耗很低，甚至可以超越Onlog(n)级别的算法；怎么实现呢，我们逐个来看看(各排序耗时PK在最后)~~

选择排序

选择排序的主体实现思路：从数组的第一个成员开始逐个遍历，找到最小那个放到第一个位置，以此类推；

// 选择排序
// 这里设置了泛型(如对泛型不了解，可以简单理解为int)
template<typename DT>
void selectSort(DT arr[], int n) {for(int i=0; i<n; i++) {int minIndex = i;for(int j=i; j<n; j++) {if(arr[j] < arr[minIndex]) {minIndex = j;}}swap(arr[i], arr[minIndex]);}
}

简单排序的优化实现：一次性找到最大和最小值

// 选择排序
template<typename DT>
void selectSort(DT arr[], int n) {// 设置初始左边界和右边界int left = 0;int right = n-1;// left < right说明序列还有成员未排序，循环while(left < right) {int minIndex = left;int maxIndex = right;
//      先将当前判断的头尾两个值的大小设定好if(arr[minIndex] > arr[maxIndex]) {swap(arr[minIndex],arr[maxIndex]);}
//      一次遍历获取当前最大或最小值，当前左右边界为未排序区间，for(int i=left+1;i<right;i++) {if(arr[i] < arr[minIndex]) {minIndex = i;} else if(arr[i] > arr[maxIndex]) {maxIndex = i;}}swap(arr[minIndex],arr[left]);swap(arr[maxIndex],arr[right]);left++;right--;}
}

冒泡排序

  冒泡排序的主体实现思路：从第一个数组成员开始，从左到右两两比较，如果出现前面的成员数据比后面的小则交换数据，遍历一次就能在右边界处放置最大值，然后右边界减1，继续遍历直到数组有序；这里有一个小技巧，就是设置一个标记，如果在一次遍历中没有进行一次数据交换，说明序列已有序，那么就可以通过这个标记判断是否在一次遍历中有出现数据交换了，具体实现鼠标滚起来；

//冒泡排序法
template <typename T>
void bubbleSort(T arr[], int n) {// 设置标记bool swapped;//  如果一次循环过程中，没有一次成员数据交换，说明序列已有序do {swapped = false;for (int i = 0; i < n-1; i++) {if (arr[i] > arr[i + 1]) {swap(arr[i], arr[i + 1]);swapped = true;}}// 标记是否改为true，判断是否需要继续循环排序}while(swapped);
}

冒泡排序的优化实现：记录上一次排序最后出现有成员数据交换的位置作为右边界，因为右边界后续的序列已有序

//冒泡排序法
template <typename T>
void bubbleSort(T arr[], int n) {//  bool swapped;//  将bool swapped优化为int lastSwapped，记录最后一次交换的位置，而不是记录是否有交换//	在交换的过程中，可能只在中间进行了交换，这样就说明后面的序列已经有序，不用再比较了int lastSwapped;do {//swapped = false;lastSwapped = 0;for (int i = 0; i < n-1; i++) {if (arr[i] > arr[i + 1]) {swap(arr[i], arr[i + 1]);lastSwapped = i+1;}}//	更新右边界，有边界往后序列已有序n = lastSwapped;}while(lastSwapped > 0);
}

插入排序

  插入排序的主体实现思路：来来来，打牌！这就是一个打牌排序法，打牌的时候，一般习惯就是把同花色的牌放一起，而且会从左到右按序拿着，回想一下这个过程，会发现是摸一张就将这张插入到该在的位置；插入排序也就是从左到右遍历，一边遍历，一边将右边遍历到序列成员插入到左边已经排好序的序列中

//插入排序法
template <typename T>
void insertSort(T arr[], int n) {//	i作为右边待排序的序列成员，j作为左边已有序的序列的右边界for(int i=1;i<n;i++) {//	插入过程，从左边序列的右边开始比较，左边比右边大就交换for(int j=i;j>0;j--) {if(arr[j] < arr[j-1]) {swap(arr[j],arr[j-1]);} else {break;}}}
}

插入排序的优化实现：基础版的插入排序实现起来很简单，但是有一个弊端，试想一下打牌的时候，为了把新摸的牌放到这牌该在的位置，会不会在手中的牌从右到左一个个位置插过来，直到这个牌到位了呢？那是一个连想想都觉得尴尬的举动，所以实际实现时大可减少这些不必要的数据交换，这就使得插入排序的效率得到了质的飞跃，在面对基本有序的序列时，插入排序甚至干掉了复杂的O(nlog(n))级别的算法；

//插入排序法
template <typename T>
void insertSort(T arr[], int n) {for(int i=1;i<n;i++) {
//      改成每次插入比较时，只将较大的值往后挪，而插入的值先记着，找到位置再插入//	记录需插入序列成员T candidate = arr[i];
//      注意这里j要在外面声明，如果在for里面声明j只在for内部可见int j;// if-else可以整合到for循环中，后续希尔排序有类似整合for(j=i;j>0;j--) {// 需插入数据不是当前最大值时，不再交换，而是让当前对比的大数后移if(arr[j-1] > candidate) {arr[j] = arr[j-1];//	需插入数据已经找到位置了，跳出循环} else {break;}}//	将数据插入arr[j] = candidate;}
}

希尔排序

  希尔排序的主体实现思路：插入算法的黄金马甲，以低耗时的遍历查询次数换取更为耗时的数据赋值次数的减少；前面的三种排序，序列中一个成员要到有序的位置必须进行逐个比较，比较后，如果发现位置要变，则必定会出现数据的交换或至少是赋值(挪位)；然而如果知道最后一个(或靠后)数据是最小的(或几乎最小的)，那么最好的做法肯定就是直接跳过和中间序列成员的比较，将后面这个成员跳到前面去比较，这样就减少了很多不必要的挪位；希尔算法就是通过先以大间隔进行比较，让远离有序位置的成员跳跃性地进行比较到所需位置的附近，从大间隔的比较然后逐渐到间隔为1的比较，从而达到序列有序；这个过程虽然增加了查询次数，但是因为查询比赋值耗时要低很多，所以实际意义很大；但需要注意的时候在面对基本有序序列时，插入排序仍然最优，因为面对基本有序序列，插入排序的机制让插入排序只需比较，很少赋值，而希尔排序增加的查询时间在这个时候就不够给力了，那基本有序到什么程度呢，我肯定不会告诉你大概时100000个数据中只有200个数据未排好序时，超过了时还是希尔牛；

// 希尔排序法
template<typename T>
void shellSort(T arr[], int n) {// 计算 increment sequence: 2, 4, 8, 16, 32, 64, int D = 2;while( D < n/2 ) {D *= 2;}while(D >= 1) {// 开始插入排序，对每个数据逐个按D个间隔进行排序，对于0到D的数据，在下面的for循环中考虑进去了for(int i=1;i<n;i++) {T candidate = arr[i];int j;//	区别与常规的插入排序，这里比较插入时不是直接以1的间隔比较，而是按D的区间进行比较for(j=i;j>=D && candidate<arr[j-D];j-=D) {arr[j] = arr[j-D];}arr[j] = candidate;}D /= 2;}
}

希尔排序的优化实现：希尔排序本身已经优化后的，但是大神的世界没有足够优化的说法，之前用于增加排序间隔的序列时随意用2的幂次来获取的(也可以自己搞个什么序列)，但是随便搞的序列有个问题，就是可能会导致重复查询，如在8的间隔时已经对比过第4个和第12个序列成员了，到了4的间隔时，会对比第4个，第8个，第12个序列成员，这样通过第8个成员，第4个和第12个又比了一次，Sedgewick增量序列则很好地解决了这个问题；

// 希尔排序法
template<typename T>
void shellSort(T arr[], int n) {//	Sedgewick序列，值演示了17个，适用于最多100万个数据的序列int SedgewickSeq[17] = {1,5,19,41,109,209,505,929,2161,3905,8929,16001,36289,64769,146305,260609,587521};int index = 16;//while(D >= 1) {while(index >= 0) {int D = SedgewickSeq[index];// 开始插入排序，对每个数据逐个按D个间隔进行排序，对于0到D的数据，在下面的for循环中考虑进去了for(int i=1;i<n;i++) {T candidate = arr[i];int j;for(j=i;j>=D && candidate<arr[j-D];j-=D) {arr[j] = arr[j-D];}arr[j] = candidate;}//D /= 3;index--;}
}

简单排序性能PK赛

比赛规则：

1. 对10万个数据进行排序；
2. 分随机数序列和基本有序序列两场比赛；
3. 基本有序序列的未有序数据数量是200个；
4. 所有排序法均已优化；
5. 从上到下是选择排序、冒泡排序、插入排序、希尔排序；

随机数序列：
selectSort:5.686
bubbleSort:34.211
insertSort:5.556
shellSort:0.019
基本有序序列：
selectSort:5.711
bubbleSort:0.975
insertSort:0.005
shellSort:0.006

比赛结果：

• 无论序列怎么变，希尔基本完胜，除了在基本有序上稍逊插入排序一点点；
• 原始三大简单排序优化后的插入排序最优；
• 选择排序在随机数序列上表现突出，冒泡排序则在基本有序上可圈可点；
• 插入排序无论是在查询还是赋值的次数上都少于另外两种原始简单排序；选择排序不管是否基本有序都要进行那么多的查询，所以耗时稳定；冒泡排序数据交换很多，查询较少，所以对随机序列略显乏力，对基本有序序列因数据交换大量减少，性能大幅提升；
• 比赛结果供菜鸟参考，大神点评；