一，各排序算法的思想及其稳定性
以下排序算法的排序结果若无特殊说明均为升序，swap函数的具体实现如下，每次的排序算法不再重复。（吐槽：多年后的今天来看，尼玛，都忘了，看不懂了！真佩服自己）
void swap(int *a, int i, int j) //交换两个数
{
if(i==j)
return;
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}1，八大经典排序算法
(1)冒泡排序
依次比较相邻的数据，将小数据放在前，大数据放在后；即第一趟先比较第1个和第2个数，大数在后，小数在前，再比较第2个数与第3个数，大数在后，小数在前，以此类推则将最大的数"滚动"到最后一个位置；第二趟则将次大的数滚动到倒数第二个位置......第n-1(n为无序数据的个数)趟即能完成排序。
以下面5个无序的数据为例：
40 8 15 18 12 （文中仅细化了第一趟的比较过程）
第1趟: 8 15 18 12 40
第2趟: 8 15 12 18 40
第3趟: 8 12 15 18 40
第4趟: 8 12 15 18 40
void bubblesort(int *arr,int nsize)
{
//排序，从i开始排，总是在[i+1,nsize]去寻找比当前元素小的，并且交换，使得当前位置的值总是其后面最小的。
for (int i = 0; i < nsize; i++)
for (int j = i + 1; j < nsize; j++)
if (arr[i] > arr[j]) swap(arr, i,j);
}(2)选择排序
以升序为例，比如在一个长度为N的无序数组中，
在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，
第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......
第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，
至此选择排序完成。
以下面5个无序的数据为例：
56 12 80 91 20（文中仅细化了第一趟的选择过程）
第1趟：12 56 80 91 20
第2趟：12 20 80 91 56
第3趟：12 20 56 91 80
第4趟：12 20 56 80 91
核心函数：
void selectsort(int *arr, int nsize)
{
for (int i = 0; i < nsize; i++)
{
//arr[i+1....nsize-1]中找到当前最小值及其位置（准备与当前a[i]调换）
int min = arr[i];
int minpos = i;
for (int j = i + 1; j < nsize; j++)
{
if (arr[j] < min)
{
min = arr[j]; //当前最小值
minpos = j;//记录当前最小值的位置
}
}
swap(arr, i, minpos);//交换最小值位置，a[0....i]已经有序
}
}tip：
冒泡法和选择排序很像，两者区别在于：
冒泡排序是每一次都可能要交换，而选择排序是在比较时记下a[i]的位置 最后来交换
所以他们的交换过程是不一样的，但查找的过程是一样的。
所以选择排序的效率比冒泡法只高不低...
(3)插入排序
像扑克摸牌一样，插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。
以下面5个无序的数据为例：
65 27 59 64 58 （文中仅细化了第四次插入过程）
第1次插入: 27 65 59 64 58
第2次插入: 27 59 65 64 58
第3次插入: 27 59 64 65 58
第4次插入: 27 58 59 64 65
void insertsort(int *arr, int nsize)
{
int i, j, key;
for (i = 1; i<nsize; i++)//控制需要插入的元素
{
key = arr[i]; //key为当前要插入的元素，将其插入到有序段arr[0,i-1]
j = i - 1;
while (j >= 0 && arr[j] > key) //查找要插入的位置,循环结束时则找到插入位置j
{
arr[j+1] = arr[j]; //移动元素的位置.供要插入元素使用
j--;
}
arr[j+1] = key; //插入指定元素到指定位置
}
}(4)快速排序
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，该方法的基本思想是：
1．先从数列末尾取出一个数作为基准元。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
//手动快速默写快排：先划界，再分治....
int quickPartion(int *arr, int low, int high)
{
int pos = rand() % (high - low + 1) + low;
swap(arr, pos, high);//将末尾的元素随机化,防止极端情况
int key = arr[high];//总是将末尾元素选为关键化界元
int i = low - 1;//总是记录比key小的元素最前面的位置
for (int j = low; j <= high - 1; j++)
{
if (arr[j] <= key)
swap(arr, ++i, j);
}
swap(arr, ++i, high);
return i;//返回“中间位置”
}
void QuickSort(int *arr, int low, int high)
{
if (low < high)
{
int mid = quickPartion(arr, low, high);
QuickSort(arr, low, mid - 1);
QuickSort(arr, mid + 1, high);
}
}(5)归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
核心函数：
//分治法的合并函数
//arr[low...mid]与arr[mid+1...high]相合并
void Merge(int *arr, int low, int mid, int high)
{
int leftlen = mid - low + 1;//arr[low...mid]的长度
int rightlen = high - mid;//arr[mid+1...high]的长度
int *L = new int[leftlen + 1];//每次归并时都在动态申请内存，这里可以优化
int *R = new int[rightlen + 1];
L[leftlen] = INT_MAX;//末尾均是哨兵元素
R[rightlen] = INT_MAX;
//赋值，准备有序放入arr[low.....high]
int i = 0;
for (; i < leftlen; i++)
L[i] = arr[low + i];
int j = 0;
for (; j < rightlen; j++)
R[j] = arr[mid + j + 1];
//有序放入arr[low.....high]
i = 0; j = 0;
for (int k = low; k <= high; k++)
{
if (L[i] <= R[j])//谁更小，谁就放入arr[k]中
arr[k] = L[i++];
else
arr[k] = R[j++];
}
delete[] L; L = NULL;
delete[] R; R = NULL;
}
//合并排序法（分治法）
void MergeSort(int *arr, int low, int high)
{
if (low < high)
{
int mid = (low + high) / 2;
MergeSort(arr, low, mid);
MergeSort(arr, mid + 1, high);
Merge(arr, low, mid, high);
}
}(6)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
//希尔排序
void ShellSort(int *a,int nlen)
{
int gap = nlen ;
while (gap>1)
{
gap = gap / 3 + 1;
for (int i = gap; i < nlen; ++i)
{
int temp = a[i]; //暂存关键数据
int j = i;
while (j - gap >= 0 && temp < a[j - gap])
{
a[j] = a[j - gap]; //后移
j = j - gap; //前置索引
}
a[j] = temp;
}
}
}(7)堆排序
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
//保持堆的性质
//在数组arr中以位置i为入口维护最大堆性质（根节点总是更大）
void KeepMaxHeap(int *a, int i, int heapsize) //使a[i]这个元素下降（如果不满足最大根要求的话）
{
int l = 2*i+1;
int r = 2*i+2;
//找到当前入口位置i及其左右子之间的较大者，如果不是当前i位置的值最大，将会交换并重新开始调整
int largest =i;
if (l <= heapsize && a[l]>a[i])//与左子比
largest = l;
if (r <= heapsize && a[r]>a[largest])//将较大者与右子比
largest = r;
if (largest != i)
{
swap(a,i,largest);
KeepMaxHeap(a, largest, heapsize);
}
}
//创建堆,将数组调整为最大堆
void BuildMaxHeap(int *a,int nsize)
{
int heapsize = nsize - 1;
for (int i = heapsize / 2; i >= 0; i--)
KeepMaxHeap(a, i, heapsize);//heapsize/2+1到a.size-1的整数都是树叶，所以只需对0到heapsize/2作处理
}
//堆排序
void HeapSort(int *a,int nsize)
{
BuildMaxHeap(a,nsize);//使数组成为最大堆
int heapsize = nsize-1;
for (int i = nsize - 1; i>0; i--)
{
swap(a,0, i);
heapsize--;//叶子将逐渐“脱离”
KeepMaxHeap(a, 0, heapsize);//保持堆的性质
}
}(8)计数排序
假设数序列中小于元素a的个数为n，则直接把a放到第n+1个位置上。当存在几个相同的元素时要做适当的调整，因为不能把所有的元素放到同一个位置上。计数排序假设输入的元素都是0到k之间的整数。
计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计算时间下界不再是Ω(nlogn)。
对每一个输入元素x，确定小于x的元素的个数，那样排序之后，x在最终输出数组中的位置就可以确定了。
例如：如果有17个元素小于x，则x就位于第18个输出的位置上。
//计数排序
void CountSort(int *a, int len)
{
int nLen = len;
int* Cout = new int[nLen]; //申请空间,用于计数,被排序的数一定要是[0,nLen-1]之间的数（可包括）
//初始化记数为0
for (int i = 0; i < nLen; ++i)
Cout[i] = 0;
//统计元素出现次数计数。即数组元素a[i]的出现次数,将其结果存放在Cout[a[i]]中。
for (int i = 0; i < nLen; ++i)
++Cout[a[i]];
//统计小于等于当前位置i的元素个数
for (int i = 1; i < nLen; ++i)
Cout[i] += Cout[i - 1];
int* Sort = new int[nLen]; //申请空间，用于存放排序结果
for (int i = 0; i < nLen; ++i)
{
//把数据放在指定位置。因为pCout[pData[i]]的值就是不比他大数据的个数。
//为什么要先减一，因为pCout[pData[i]]保存的是不比他大数据的个数中包括了
//他自己，我的下标是从零开始的!所以要先减一。
--Cout[a[i]]; //因为有相同数据的可能，所以要把该位置数据个数减一。
Sort[Cout[a[i]]] = a[i];
}
//排序结束，复制到原来数组中。
for (int i = 0; i < nLen; ++i)
a[i] = Sort[i];
//释放申请的空间。
delete[] Cout;
Cout = NULL;
delete[] Sort;
Sort = NULL;
}2，排序算法小结
综上，得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
而冒泡排序、插入排序、计数排序、归并排序和基数排序是稳定的排序算法。还有一些排序算法我没有进行
二，C++模板实现
1,程序说明
1），本程序实现了若干经典排序算法性能（运行时间）比较
2），实现了在不同规模（元素个数）下的性能比较
3），实现了对移动次数和比较次数的统计（间接说明性能）
4），实现了数据混乱类型的选择
注：本程序有可能有bug，非绝对正确，发现过错误，未调试完！
2,AllSort.h代码如下
#include "iostream"
#include "vector"
using namespace std;
template<class DataType>
class AllSort
{
public:
AllSort()
{
//移动次数初始化
countSortMove=0;
//比较次数初始化
countSortCmp=0;
//初始化数据时的不重复个数
countNum=5;
}
~AllSort()
{
}
//打印数组
void printArray(vector<DataType> &a,bool isPrint);
//交换元素
void swap(DataType *a,DataType *b);
//初始化数组
void InitArr(vector<DataType> &a,int len,int arrType);
//冒泡排序法
void BubbleSort(vector<DataType> &a, int l, int r, bool Up=true);
//插入排序法
void InsertSort(vector<DataType> &a, int l, int r, bool Up=true);
//快速排序法
void QuickSort(vector<DataType> &a, int l, int r, bool Up=true);
//划界
int Partition(vector<DataType> &a, int l, int r, bool Up=true);
//随机快速排序法
void RandQuickSort(vector<DataType> &a, int l, int r, bool Up=true);
//随机划界
int RandPartition(vector<DataType> &a, int l, int r, bool Up=true);
//三者取中快速排序法
void thrWayQuickSort(vector<DataType> &a, int l, int r, bool Up=true);
//三者取中划界
int thrWayPartition(vector<DataType> &a, int l, int r, bool Up=true);
//分而治之排序法
void MergeSort(vector<DataType> &a, int l, int r, bool Up=true);
void Merge(vector<DataType> &a, int p, int q, int r,bool Up=true);
//计数排序
void CountSort(vector<DataType> &a,int arrType,int len,bool Up=true);
//洗牌策略随机打乱一个数组中的n个元素
void randArray(vector<DataType> &a, unsigned int n,int isRand);
//选择排序法
void SelectSort(vector<DataType> &a, int l, int r, bool Up=true);
//希尔排序
void ShellSort(vector<DataType> &a,int low, int high,bool Up=true);
//堆中的左子
int Left(int i);
//堆中的右子
int Right(int i);
//保持堆性质
void KeepMaxHeap(vector<DataType> &a, int len,int heapsize,bool Up);
//建堆
void BuildMaxHeap(vector<DataType> &a,bool Up);
//堆排序
void HeapSort(vector<DataType> &a,bool Up);
int getSortCount(bool IsMove)
{
if (IsMove)
{
return countSortMove;
}else
{
return countSortCmp;
}
}
void beforSort()
{
//移动次数初始化
countSortMove=0;
//比较次数初始化
countSortCmp=0;
}
private:
//移动次数
int countSortMove;
//比较次数
int countSortCmp;
//初始化数据时的不重复数据个数
int countNum;
};
//交换元素
template <typename DataType>
void AllSort<DataType>::swap(DataType *a,DataType *b)
{
DataType temp;
temp =*a;
*a=*b;
*b=temp;
}
//交换元素
template <typename DataType>
void AllSort<DataType>::InitArr(vector<DataType> &a,int len,int arrType)
{
if (arrType == 1)
{
for (int i=0;i<len;i++)
{
a.push_back(i);
}
}else if(arrType == 2)
{
for (int i=0;i < len;i++)
{
int key=i%countNum;
a.push_back(key);
}
}
}
// 随机打乱一个数组n个元素
template <typename DataType>
void AllSort<DataType>::randArray(vector<DataType> &a,unsigned int n,int isRand)
{
if ( n > a.size() )
{
cerr<<"无法打乱指定数量的元素"<<endl;
exit(1);
}
if (isRand == 1)//随机打乱
{
unsigned int index, i;
for (i = 0; i < n; i++)//将数组中的每一个元素都进行随即打乱
{
index = rand() % n;//残生0到n-1之间的随机位置数
if (index != i)
{
swap(&a[i],&a[index]);
}
}
}else if(isRand == 2)//升序
{
bool upflag=true;
this->ShellSort(a,0,a.size()-1,upflag);
}else if(isRand == 3) //降序
{
bool upflag=false;
this->ShellSort(a,0,a.size()-1,upflag);
}else if(isRand == 4)
{
unsigned int gap=5;
unsigned int index, i;
for (i = 0; i < n; i++)//将数组中的每一个元素都进行随即打乱
{
index = rand()%gap + i;//残生i到j之间的随机位置数
if ( index != i&& index < n)
{
swap(&a[i],&a[index]);
}
}
}else
{
cerr<<"isRand参数错误！来自randArray（）函数"<<endl;
return;
}
}
//打印数组
template <typename DataType>
void AllSort<DataType>::printArray(vector<DataType> &a,bool isPrint)
{
if (isPrint)
{
cout<<"排序或打乱结果为： ";
for(unsigned int i = 0; i < a.size(); i++ )
{
cout << a[ i ]<<" ";
if ((i+1)%27 == 0)
{
cout<<endl;
}
}
cout<<endl;
}
}
//希尔排序
template <typename DataType>
void AllSort<DataType>::ShellSort(vector<DataType> &a,int low, int high,bool Up)
{
beforSort();
int gap = high-low+1;
while (gap>1)
{
gap = gap/3+1;
for(int i = low + gap; i <= high; ++i)
{
int temp = a[i]; //暂存关键数据
int j = i;
countSortCmp++;
if (Up)
{
while(j-gap >= low && temp < a[j-gap])
{
a[j] = a[j-gap]; //后移
j = j-gap; //前置索引
countSortCmp++;
countSortMove++;
}
}else
{
while(j-gap >= low && temp > a[j-gap])
{
a[j] = a[j-gap]; //后移
j = j-gap; //前置索引
countSortCmp++;
countSortMove++;
}
}
a[j] = temp;
countSortMove=countSortMove+2;
}
}
}
//随机快速排序划界函数
int stepRandQuickSort=1;
template <typename DataType>
void AllSort<DataType>::RandQuickSort(vector<DataType> &a, int low, int high, bool Up)
{
int pivotKey=0;
if ( stepRandQuickSort ==1)
{
beforSort();
stepRandQuickSort=0;
}
if (low < high)
{
pivotKey=RandPartition(a,low,high,Up);
RandQuickSort(a,low,pivotKey-1,Up);
RandQuickSort(a,pivotKey+1,high,Up);
}
}
//随机快速排序的中点函数
template <typename DataType>
int AllSort<DataType>::RandPartition(vector<DataType> &a, int low, int high, bool Up)
{
int randPivotKey=rand()%(high-low+1)+low;
this->swap(&a[randPivotKey],&a[high]);
countSortMove=countSortMove+3;
return Partition(a,low,high,Up);
}
int stepthrWayQuickSort=1;
template <typename DataType>
void AllSort<DataType>::thrWayQuickSort(vector<DataType> &a, int low, int high, bool Up)
{
if (stepthrWayQuickSort ==1)
{
beforSort();
stepthrWayQuickSort=0;
}
int pivotKey=0;
if (low < high)
{
pivotKey=thrWayPartition(a,low,high,Up);
thrWayQuickSort(a,low,pivotKey-1,Up);
thrWayQuickSort(a,pivotKey+1,high,Up);
}
}
//快速排序的中点函数
template <typename DataType>
int AllSort<DataType>::thrWayPartition(vector<DataType> &a, int low, int high, bool Up)
{
int PivotKey1=rand()%(high-low+1)+low;
int PivotKey2=rand()%(high-low+1)+low;
int PivotKey3=rand()%(high-low+1)+low;
int midkey=PivotKey1;
if (PivotKey1 <= PivotKey2 && PivotKey2 <= PivotKey3 )
{
midkey=PivotKey2;
countSortCmp=countSortCmp+2;
}else if( PivotKey2 <= PivotKey1 && PivotKey1 <= PivotKey3 )
{
midkey=PivotKey1;
countSortCmp=countSortCmp+2;
}else
{
midkey=PivotKey3;
}
this->swap(&a[midkey],&a[high]);
countSortMove=countSortMove+3;
return Partition(a,low,high,Up);
}
//快速排序
int stepQuickSort=1;
template <typename DataType>
void AllSort<DataType>::QuickSort(vector<DataType> &a, int low, int high, bool Up)
{
if (stepQuickSort ==1)
{
beforSort();
stepQuickSort=0;
}
int mid=0;
if (low < high)
{
mid=Partition(a,low,high,Up);
QuickSort(a,low,mid-1,Up);
QuickSort(a,mid+1,high,Up);
}
}
//快速排序的划界函数
template <typename DataType>
int AllSort<DataType>::Partition(vector<DataType> &a, int low, int high, bool Up)
{
int pivotkey=a[high];//选择主元,即基准元素
int i=low-1;
if (Up)
{
for ( int j = low;j < high;j++)
{
countSortCmp++;
if (a[j] < pivotkey && i != j )
{
i++;
swap(&a[i],&a[j]);
countSortMove=countSortMove+3;
}
}
}else
{
for ( int j = low;j < high;j++)
{
countSortCmp++;
if (a[j] > pivotkey)
{
i++;
swap(&a[i],&a[j]);
countSortMove=countSortMove+3;
}
}
}
i++;
swap(&a[i],&a[high]);
countSortMove=countSortMove+3;
return i;
}
int stepMerge=1;
//合并排序法（分治法）
template <typename DataType>
void AllSort<DataType>::MergeSort(vector<DataType> &a, int low, int high, bool Up)
{
if (stepMerge==1)
{
beforSort();
stepMerge=0;
}
if (low < high)
{
int mid=(low+high)/2;
MergeSort(a,low,mid,Up);
MergeSort(a,mid+1,high,Up);
Merge(a,low,mid,high,Up);
}
}
//分治法的合并函数
template <typename DataType>
void AllSort<DataType>::Merge(vector<DataType> &a, int low, int mid, int high,bool Up)
{
int n1=mid -low+1,n2=high-mid;
long Max=99999999;
long Min=-99999999;
int *L=new int[n1+1];
int *R=new int[n2+1];
if ( L == NULL || R == NULL )
{
exit(1);
}
int i=0;
for ( ;i < n1;i++ )
{
L[i]=a[low+i];
countSortMove++;
}
int j=0;
for ( ;j < n2;j++ )
{
R[j]=a[mid+j+1];
countSortMove++;
}
i=0;j=0;
int k=0;
if (Up)
{
L[n1]=Max;//哨兵元素位置
R[n2]=Max;
for ( k = low; k <= high ; k++ )
{
if ( L[i] <= R[j] )
{
a[k]=L[i];
i++;
countSortMove++;
}else
{
a[k]=R[j];
j++;
countSortMove++;
}
countSortCmp++;
}
}else
{
L[n1]=Min;//哨兵元素位置
R[n2]=Min;
for ( k = low; k <= high ; k++ )
{
if ( L[i] >= R[j] )
{
a[k]=L[i];
i++;
countSortMove++;
}else
{
a[k]=R[j];
j++;
countSortMove++;
}
countSortCmp++;
}
}
delete[] L;
delete[] R;
}
//选择排序法
template <typename DataType>
void AllSort<DataType>::SelectSort(vector<DataType> &a, int low, int high, bool Up)
{
beforSort();
DataType min;
DataType max;
for(int i = low ; i <= high; i++)
{
//找到最小值及其位置（准备与a[i]调换）
min = a[i];
max = a[i];
int index = i;
for(int j=i+1;j <= high;j++)
{
countSortCmp++;
if (Up)
{
if(a[j] < min)
{
min = a[j]; //当前最小值
index = j;//当前最小值的位置
countSortMove++;
}
}else
{
if(a[j] > max)
{
max = a[j]; //当前最大值
index = j;//当前最大值的位置
countSortMove++;
}
}
}
if (Up)
{
swap(&a[i],&a[index]);
countSortMove=countSortMove+3;
}else
{
swap(&a[i],&a[index]);
countSortMove=countSortMove+3;
}
}
}
//冒泡排序
template <typename DataType>
void AllSort<DataType>::BubbleSort(vector<DataType> &a, int l, int r, bool Up)
{
beforSort();
bool flag=false;
for ( int i = l;i < r;i++)
{
flag=false;
for ( int j = r;j >= i+1;j--)
{
countSortCmp++;
if (Up)
{
if (a[j-1]>a[j]) //调换次序
{
this->swap(&a[j-1],&a[j]);
countSortMove=countSortMove+3;
flag=true;
}
}else
{
if (a[j-1]<a[j])
{
this->swap(&a[j-1],&a[j]);
countSortMove=countSortMove+3;
flag=true;
}
}
}
if (!flag)
{
break;
}
}
}
//插入排序
template <typename DataType>
void AllSort<DataType>::InsertSort(vector<DataType> &a, int l, int r, bool Up)
{
beforSort();
DataType key;
if (Up)
{
for ( int i = l+1 ; i <= r;i++ )
{
key=a[i];
int j=i-1;
countSortCmp++;
while ( j >= l && a[j] > key )
{
a[j+1]=a[j];
j--;
countSortMove++;
countSortCmp++;
}
a[j+1]=key;
countSortMove=countSortMove+2;
}
}
else
{
for ( int i = l+1 ; i <= r;i++ )
{
key=a[i];
int j=i-1;
countSortCmp++;
while (j >= l && a[j] < key)
{
a[j+1]=a[j];
j--;
countSortMove++;
countSortCmp++;
}
a[j+1]=key;
countSortMove=countSortMove+2;
}
}
}
template <typename DataType>
int AllSort<DataType>::Left( int i)
{
return 2*i+1;
}
template <typename DataType>
int AllSort<DataType>::Right( int i)
{
return 2*i+2;
}
//保持堆的性质
template <typename DataType>
void AllSort<DataType>::KeepMaxHeap(vector<DataType> &a, int i,int heapsize,bool Up) //使a[i]这个元素下降（如果不满足最大根要求的话）
{
int l=Left(i);
int r=Right(i);
int largest=0;
int min=0;
if (Up)
{
if (l<= heapsize && a[l]>a[i])//与左子比
{
largest=l;
}
else
{
largest=i;
}
if (r<= heapsize && a[r]>a[largest])//将较大者与右子比
{
largest=r;
}
}else
{
if (l<= heapsize && a[l]<a[i])//与左子比
{
min=l;
}
else
{
min=i;
}
if (r<= heapsize && a[r]<a[min])//将较大者与右子比
{
min=r;
}
}
countSortCmp=countSortCmp+2;
if (Up)
{
if (largest!=i)
{
swap(&a[i],&a[largest]);
countSortMove=countSortMove+3;
KeepMaxHeap(a,largest,heapsize,Up);
}
}else
{
if (min!=i)
{
swap(&a[i],&a[min]);
countSortMove=countSortMove+3;
KeepMaxHeap(a,min,heapsize,Up);
}
}
}
//创建堆,将数组调整为最大堆
template <typename DataType>
void AllSort<DataType>::BuildMaxHeap(vector<DataType> &a,bool Up)
{
int heapsize=a.size()-1;
for (int i=heapsize/2 ; i>=0 ;i-- )
{
KeepMaxHeap(a,i,heapsize,Up);//heapsize/2+1到a.size-1的整数都是树叶，所以只需对0到heapsize/2作处理
}
}
//堆排序
template <typename DataType>
void AllSort<DataType>::HeapSort(vector<DataType> &a,bool Up)
{
beforSort();
BuildMaxHeap(a,Up);//使数组成为最大堆
int heapsize=a.size()-1;
for (int i=a.size()-1;i>0;i--)
{
swap(&a[0],&a[i]);
countSortMove=countSortMove+3;
heapsize--;
KeepMaxHeap(a,0,heapsize,Up);//保持堆的性质
}
}
//计数排序
template <typename DataType>
void AllSort<DataType>::CountSort(vector<DataType> &a,int arrType,int len,bool Up)
{
int nLen=len;
int k=0;
if (arrType==1)
{
k=nLen;
}else
{
k=countNum;
}
countSortCmp=0;
DataType* Cout = new DataType[nLen]; //申请空间,用于计数
//初始化记数为0
for (int i = 0; i < k; ++i)
{
Cout[i] = 0;
}
//统计元素出现次数计数。即数组元素a[i]的出现次数,将其结果存放在Cout[a[i]]中。
for (int i = 0; i < nLen; ++i)
{
++Cout[a[i]];
}
//统计小于等于当前位置i的元素个数
for (int i = 1; i < nLen; ++i)
{
Cout[i] += Cout[i - 1];
}
DataType* Sort =new DataType[nLen]; //申请空间，用于存放排序结果
for (int i = 0; i < nLen; ++i)
{
//把数据放在指定位置。因为pCout[pData[i]]的值就是不比他大数据的个数。
//为什么要先减一，因为pCout[pData[i]]保存的是不比他大数据的个数中包括了
//他自己，我的下标是从零开始的!所以要先减一。
--Cout[a[i]]; //因为有相同数据的可能，所以要把该位置数据个数减一。
Sort[Cout[a[i]]] = a[i];
}
//排序结束，复制到原来数组中。
if (Up==true)
{
for (int i = 0; i < nLen; ++i)
{
a[i] = Sort[i];
}
}else
{
for (int i = 0; i < nLen; ++i)
{
a[i] = Sort[nLen-i-1];
}
}
//释放申请的空间。
delete[] Cout;
Cout=NULL;
delete[] Sort;
Sort=NULL;
}
3，主测试代码：
[html] view plain copy print?
// ConsoleAppAllSort.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "iostream"
#include <vector>
#include <windows.h>
#include "AllSort.h"
#include "stdio.h"
#include<algorithm>
#include<functional>
using namespace std;
LARGE_INTEGER freq;
LARGE_INTEGER startTime, stopTime;
double time;
void help(int len,bool Up,int IsRand,int arrType);
void initArr();
int _tmain(int argc, _TCHAR* argv[])
{
system("color 0A");
AllSort<int> sort;//定义排序类对象
vector<int> arr; //定义并初始化一个容器,进行数组操作
int len=10; //控制数组长度
char ans='y';
do
{
cout<<"请输入数组初始化类型及元素个数：（1为元素完全不重复，2为有大量重复值）"<<endl;
int arrType=1;//1为完全不重复，2为大量重复值
cin>>arrType>>len;
sort.InitArr(arr,len,arrType);
//各大开关
cout<<"请输入排序类型：0为降序，1为升序"<<endl;
bool upflag=false;//控制所有排序的升排或者降排的开关
cin>>upflag;
cout<<"请输入数组的随机类型：1为纯随机，2为升序，3为降序,4为小随机"<<endl;
int isRand=1;//1为纯随机，2为升序，3为降序,4为小随机
cin>>isRand;
cout<<"是否打印排序结果：0为否，1为是"<<endl;
bool isPrint=false;//是否print
cin>>isPrint;
bool isMove=true;
help(len,upflag,isRand,arrType);
cout<<"/**************************改进冒泡法***************************/"<<endl;
sort.randArray(arr,len,isRand);
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
sort.BubbleSort(arr,0,arr.size()-1,upflag);
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"/*******************std::sort()(注:无法统计次数)******************/"<<endl;
sort.beforSort();
sort.randArray(arr,len,isRand);
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
if (upflag)
{
std::sort(arr.begin(),arr.end(),std::less<int>());
}else
{
std::sort(arr.begin(),arr.end(),std::greater<int>());
}
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"/**************************插入法***************************/"<<endl;
sort.randArray(arr,len,isRand);//打乱数组
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
sort.InsertSort(arr,0,arr.size()-1,upflag);
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"/**************************分治法***************************/"<<endl;
sort.randArray(arr,len,isRand);//打乱数组
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
sort.MergeSort(arr,0,arr.size()-1,upflag);
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"/********************快排法(随机划界元)**********************/"<<endl;
sort.randArray(arr,len,isRand);//打乱数组
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
sort.RandQuickSort(arr,0,arr.size()-1,upflag);
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"/********************快排法(三数取中划界元)*******************/"<<endl;
sort.randArray(arr,len,isRand);//打乱数组
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
sort.thrWayQuickSort(arr,0,arr.size()-1,upflag);
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"/********************快排法(尾端划界元)*************************/"<<endl;
sort.randArray(arr,len,isRand);//打乱数组
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
sort.QuickSort(arr,0,arr.size()-1,upflag);
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"/*****************************选择法****************************/"<<endl;
sort.randArray(arr,len,isRand);//打乱数组
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
sort.SelectSort(arr,0,arr.size()-1,upflag);
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"/******************************希尔法***************************/"<<endl;
sort.randArray(arr,len,isRand);//打乱数组
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
sort.ShellSort(arr,0,arr.size()-1,upflag);
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"/******************************堆排序法***************************/"<<endl;
sort.randArray(arr,len,isRand);//打乱数组
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
sort.HeapSort(arr,upflag);
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"/******************************计数序法***************************/"<<endl;
sort.randArray(arr,len,isRand);//打乱数组
sort.printArray(arr,isPrint);
QueryPerformanceCounter(&startTime);
sort.CountSort(arr,arrType,len,upflag);
QueryPerformanceCounter(&stopTime);
sort.printArray(arr,isPrint);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"消耗时间"<<time<<"毫秒 ";
cout<<"移动次数："<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl;
cout<<"是否继续（y/n）？"<<endl;
cin>>ans;
arr.clear();
} while (ans=='y');
system("pause");
return 0;
}
void help(int len,bool Up,int IsRand,int arrType)
{
cout<<"/***********************综上所述******************************"<<endl;
cout<<"当前数组元素个数为："<<len<<endl;
cout<<"原始数组的元素特点："<<endl;
if (arrType==1)
{
cout<<" 1）无重复值"<<endl;
cout<<" 2）值分布：0-"<<len-1<<endl;
}else if(arrType==2)
{
cout<<" 1）大量重复值"<<endl;
cout<<" 2）非重复值的分布：0-5"<<endl;
}
if (IsRand == 1)
{
cout<<" 3）随机分布"<<endl;
}else if(IsRand ==2)
{
cout<<" 3) 有序：升序"<<endl;
}else if(IsRand ==3)
{
cout<<" 3) 有序：降序"<<endl;
}
else if(IsRand ==4)
{
cerr<<" 3) 小随机(总体上呈有序趋势)"<<endl;
}else
{
cerr<<"IsRand参数错误!"<<endl;
}
if (Up)
{
cout<<"各排序即将执行:升序"<<endl;
}else
{
cout<<"各排序即将执行:降序"<<endl;
}
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&startTime);
Sleep(500);
QueryPerformanceCounter(&stopTime);
time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart;
cout<<"你电脑的频率为："<<freq.QuadPart<<endl;
cout<<"你的电脑执行Sleep(500)消耗时间为："<<time<<"毫秒"<<endl;
}三，测试结果
（篇幅有限，仅展示部分结果）
四，总结：
1、冒泡排序
优点：稳定； 思想易理解，编写简单
缺点：慢，每次只能移动相邻两个数据。
2、选择排序
优点：编写简单；移动数据的次数已知（n-1次）；
缺点：比较次数多。
3、插入排序
优点：稳定，思想简单，编写简单。
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
4、希尔排序
优点：快，数据移动少；
缺点：不稳定，gap的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取，并且无法对链表排序。
5、快速排序
快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。
优点：极快，数据移动少；
缺点：不稳定。
6、归并排序
归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。
归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.
归并排序：归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。
7、堆排序：
由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：
一是建堆，二是交换数值（或者输出堆），三是排序（调整堆）。
所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。
8、计数排序：
对于数组元素集中在小范围内的整数数组排序特别快，并且也是稳定排序，但是这种排序算法缺点特别大。
参考资源：
【1】《算法导论》
【2】《维基百科》
【3】《百度文库》
【4】http://www.oschina.NET/question/1397765_159365
【5】http://www.cnblogs.com/biyeymyhjob/archive/2012/07/17/2591457.html
【6】http://blog.csdn.Net/xiazdong/article/details/8462393
【7】http://baike.baidu.com/view/297739.htm
【8】http://www.cnblogs.com/kaituorensheng/archive/2013/02/23/2923877.html
【9】http://blog.csdn.net/hguisu/article/details/7776068
【10】http://blog.csdn.net/speedme/article/details/23021467
注：
本文部分文字参考并整理自网络，代码参考并改编自算法导论.
微信
支付宝
