2013-08-22 14:55:33
八大排序方法汇总（选择排序-简单选择排序、堆排序，插入排序-简单插入排序、shell排序，交换排序-冒泡排序、快速排序，归并排序，计数排序）。
插入排序还可以和折半查找相结合，提高查找插入位置的速度，也就是折半插入排序，此处没有给出这种方法的相应代码。
对排序算法，可从以下几个方面评价：
- 时间复杂度；
- 空间复杂度；
- 稳定性。
代码（测试暂未发现问题，欢迎交流指正！）：
#include <iostream>
#include <cassert>
#include <ctime>
#include <bitset>
using namespace std; typedef int DataType;
const int MaxSize = ;
const int SortCutOff = ; //产生在[lowBound,upperBound - 1]区间的随机数
int RandomIntGenerate(int lowBound, int upperBound)
{
return (lowBound + (RAND_MAX * rand() + rand()) % (upperBound - lowBound + ) );
} //数组显示
void DisplayArray(DataType array[],int len)
{
assert(NULL != array && len > ); for (int i = ;i < len;++i)
{
cout<<array[i]<<"\t";
}
cout<<endl;
} //简单选择排序
void SelectSort(DataType *unStorted,size_t n)
{
assert(NULL != unStorted && n > ); size_t i;
size_t j;
size_t minIndex = ; for (i= ;i < n - ;++i)
{
minIndex = i;
for (j = i + ;j < n;++j)
{
minIndex = unStorted[minIndex] < unStorted[j] ? minIndex : j;
} swap(unStorted[i],unStorted[minIndex]); //没有判断i与minIndex是否相等
}
} //简单插入排序
void InsertSort(DataType *unStorted,size_t n)
{
assert(NULL != unStorted && n > ); size_t i;
int j; //不能定义为size_t,因为for循环的结束条件需要将j减为-1作为结束条件
DataType dataToInsert = ; for (i= ;i < n - ;++i)
{
dataToInsert = unStorted[i + ];
for (j = i;j >= ;--j)
{
if (unStorted[j] > dataToInsert)
{
unStorted[j + ] = unStorted[j];
}
else
{
break;
}
}
unStorted[j + ] = dataToInsert; //注意此处为j + 1，而非j
}
} //插入排序-shell排序
//简单插入排序在输入为基本有序的情况下，性能最好，
//shell排序每次大步长下的排序，相当于通过分组对数组预处理，使其基本有序
void ShellSort(DataType *unStorted,size_t n)
{
assert(NULL != unStorted && n > ); size_t step = n / ;
size_t k;
size_t i;
int j; //不能定义为size_t,因为for循环的结束条件需要将j减为-1作为结束条件
DataType dataToInsert = ; while (step >= ) //n为1时，step为0，不进入while循环就返回；
{
for (k = ;k < step;++k )
{
for (i= ;i < n - step;i += step)
{
dataToInsert = unStorted[i + step];
for (j = i;j >= ;j -= step)
{
if (unStorted[j] > dataToInsert)
{
unStorted[j + step] = unStorted[j];
}
else
{
break;
}
}
unStorted[j + step] = dataToInsert; //注意此处为j + 1，而非j
}
}
step /= ;
}
} //交换排序-冒泡排序
void BubbleSort(DataType *unStorted,size_t n)
{
assert(NULL != unStorted && n > ); size_t i;
size_t j; for (i = n - ;i >= ;--i)
{
for (j = ;j < i;++j)
{
if (unStorted[j] > unStorted[j + ])
{
swap(unStorted[j],unStorted[j + ]);
}
}
}
} //快速排序的划分函数
size_t Partion(DataType *unStorted,size_t begin,size_t end)
{
assert(begin <= end); //begin end都是定义为size_t的，因此不需要检查 size_t i = begin;
size_t j = end;
//size_t pivot = i;
size_t pivot = RandomIntGenerate(begin,end); //枢轴为随机的，使得快速排序的划分尽可能对称
swap(unStorted[i],unStorted[pivot]); while (i < j)
{
while (j > i && unStorted[j] > unStorted[i])
{
--j;
} if (j > i)
{
swap(unStorted[i],unStorted[j]);
pivot = j;
++i;
} while (i < j && unStorted[i] < unStorted[j])
{
++i;
} if (j > i)
{
swap(unStorted[i],unStorted[j]);
pivot = i;
--j;
}
}
//return i;
//return j;
return pivot;
} //交换排序-快速排序
void QuickSort(DataType *unStorted,size_t begin,size_t end)
{
assert(NULL != unStorted); //assert(begin >= 0 && end >= 0); //begin end都是定义为size_t的，因此不需要检查 if (begin >= end)
{
return;
} int mid = Partion(unStorted,begin,end); if (begin < mid)
{
QuickSort(unStorted,begin,mid - );
} //QuickSort(unStorted,begin,mid - 1); //若mid为0，size_t类型的mid减1会出问题，因此用begin < mid判断
QuickSort(unStorted,mid + ,end);
} //归并两个数组
void Merge(DataType *unStorted,size_t begin,size_t mid,size_t end)
{
assert(NULL != unStorted);
assert(begin <= mid && mid <=end); DataType *resArray = new DataType[end - begin + ];
DataType *res = resArray; size_t lowIndex = begin;
size_t highIndex = mid + ; while (lowIndex <= mid && highIndex <= end)
{
if (unStorted[lowIndex] <= unStorted[highIndex])
{
*res++ = unStorted[lowIndex++];
}
else
{
*res++ = unStorted[highIndex++];
}
} while (lowIndex <= mid)
{
*res++ = unStorted[lowIndex++];
} while (highIndex <= end)
{
*res++ = unStorted[highIndex++];
} res = resArray; for (size_t index = begin;index <= end;++index)
{
unStorted[index] = *res++;
} delete [] resArray;
} //归并排序的非递归实现，自底向上归并
void MergeSortNonRecursive(DataType *unStorted,size_t n)
{
assert(NULL != unStorted); size_t begin = ;
size_t mid = ;
size_t end = ; size_t step = ; while (step < n)
{
begin = ;
mid = begin + step - ;
end = begin+ * step - ; while (mid < n)
{
end = end > (n - ) ? (n - ) : end; //防止end越界 Merge(unStorted,begin,mid,end); begin = end + ; //不是begin = begin + step + 1;
mid = begin + step - ;
end = begin+ * step - ;
}
step *= ;
}
} //归并排序的非递归实现，自顶向下归并，分治法
void MergeSort(DataType *unStorted,size_t begin,size_t end)
{
assert(NULL != unStorted); if (begin >= end)
{
return;
} size_t mid = begin + (end - begin) / ;
MergeSort(unStorted,begin,mid);
MergeSort(unStorted,mid + ,end); //若mid为size_t类型最大值，mid + 1就会越界，此时end已经越界
Merge(unStorted,begin,mid,end);
} //堆调整
//参数n为数组中最大小标，如数组有n+1个元素，最大下标为n
//posToAdjust为需要调整的位置的下标
void HeapAdjust(DataType *unStorted,size_t n,size_t posToAdjust)
{
assert(NULL != unStorted); //在调用的函数中已经有，可以删去 size_t lchildIndex = * posToAdjust + ;
size_t rchildIndex = * posToAdjust + ; size_t maxPosition = posToAdjust; //while (lchildIndex <= n || rchildIndex <= n)
while (lchildIndex <= n) //此处只要lchildIndex <= n ，即可进入循环
{
if (lchildIndex <= n && unStorted[lchildIndex] > unStorted[maxPosition])
{
maxPosition = lchildIndex;
}
//else if (rchildIndex <= n && unStorted[rchildIndex] > unStorted[maxPosition])
if (rchildIndex <= n && unStorted[rchildIndex] > unStorted[maxPosition]) //不是else if
{
maxPosition = rchildIndex;
} if (maxPosition != posToAdjust)
{
swap(unStorted[posToAdjust],unStorted[maxPosition]); posToAdjust = maxPosition; //更新posToAdjust，可以用递归，即HeapAdjust(unStorted,n,maxPosition);
lchildIndex = * maxPosition + ;
rchildIndex = * maxPosition + ;
}
else
{
break;
}
}
} //堆排序
//参数n为数组中最大小标，如数组有n+1个元素，最大下标为n
void HeapSort(DataType *unStorted,size_t n)
{
assert(NULL != unStorted); int index; for (index = (n - ) / ;index >= ;--index) //index需要减到0，因此不能定义为size_t
{
HeapAdjust(unStorted,n,index);
} for (index = n;index >= ;--index)
{
swap(unStorted[],unStorted[index]);
HeapAdjust(unStorted,index - ,); //不是HeapAdjust(unStorted,index,0);
}
} //计数排序，基本实现
//此处的基数排序的使用场合：
//输入为正数；
// 输入不重复；
//输入的最大数与输入的个数基本相等时空间利用率最高，也就是输入为0~n内的n个不重复的正数
void CountSortBasic_1(DataType *unStorted,size_t n)
{
assert(NULL != unStorted); size_t *hash = new size_t [n + ];
size_t cnt = ;
int index = ; for (index = ;index <= n;++index)
{
hash[index] = ;
} for (index = ;index < n;++index) //index < n而非index <= n，因为此处访问的是unStorted[index]，最大下标为n-1
{
++hash[ unStorted[index] ];
} for (index = ;index <= n;++index)
{
if (hash[ index ] != ) //判断index是否出现
{
unStorted[cnt++ ] = index;
}
} delete [] hash;
} //计数排序，位图实现
void CountSort(DataType *unStorted,size_t n)
{
assert(NULL != unStorted); bitset<MaxSize> hash; size_t cnt = ;
int index = ; hash.reset(); for (index = ;index < n;++index) //index < n而非index <= n，因为此处访问的是unStorted[index]，最大下标为n-1
{
hash.set(unStorted[index]);
} for (index = ;index <= n;++index)
{
if ( hash.test(index) )
{
unStorted[cnt++ ] = index;
}
}
} //测试“脚手架”
void TestSortDriver()
{
/*DataType *unsortedArray = new DataType[MaxSize];
size_t lengthOfUnsortedArray;*/
size_t programToTest; int MinRandomInt;
int MaxRandomInt;
size_t i;
int timeStart = ;
double timeCostAverage = ; //用于计数排序时的输入
DataType unsortedArray[]= {,,,,,,,,,};
size_t lengthOfUnsortedArray = ; cout<<"please enter the length Of UnsortedArray,MinRandomInt and MaxRandomInt :"<<endl;
cin>>lengthOfUnsortedArray>>MinRandomInt>>MaxRandomInt;
cout<<"please enter the identifier of the program to test (end with ctrl+z): "<<endl;
while (cin>>programToTest)
{
for (i = ;i < lengthOfUnsortedArray;++i) //准备待排序数组
{
unsortedArray[i] = RandomIntGenerate(MinRandomInt,MaxRandomInt);
} cout<<"the unsorted array is :"<<endl;
DisplayArray(unsortedArray,lengthOfUnsortedArray); timeStart = clock();
switch (programToTest)
{
case :
cout<<"Test SelectSort..."<<endl;
SelectSort(unsortedArray,lengthOfUnsortedArray);
break; case :
cout<<"Test InsertSort..."<<endl;
InsertSort(unsortedArray,lengthOfUnsortedArray);
break; case :
cout<<"Test ShellSort..."<<endl;
ShellSort(unsortedArray,lengthOfUnsortedArray);
break; case :
cout<<"Test BubbleSort..."<<endl;
BubbleSort(unsortedArray,lengthOfUnsortedArray);
break; case :
cout<<"Test QuickSort..."<<endl;
QuickSort(unsortedArray,,lengthOfUnsortedArray - );
break; case :
cout<<"Test HeapSort..."<<endl;
HeapSort(unsortedArray,lengthOfUnsortedArray - );
break; case :
cout<<"Test MergeSortNonRecursive..."<<endl;
MergeSortNonRecursive(unsortedArray,lengthOfUnsortedArray);
break; case :
cout<<"Test MergeSort..."<<endl;
MergeSort(unsortedArray,,lengthOfUnsortedArray - );
break; case :
cout<<"Test CountSort..."<<endl;
CountSort(unsortedArray,lengthOfUnsortedArray);
break; default:
break;
} timeCostAverage = 1e9 * ( clock() - timeStart ) / ( CLOCKS_PER_SEC * lengthOfUnsortedArray );
cout<<"the average time cost per data is : "<<timeCostAverage<<" ns"<<endl; for (i = ;i < lengthOfUnsortedArray - ;++i)
{
if (unsortedArray[i] > unsortedArray[i + ])
{
cout<<"sort bug i = "<<i<<endl;
}
} cout<<"the sorted array is :"<<endl;
DisplayArray(unsortedArray,lengthOfUnsortedArray); cout<<endl;
cout<<"please enter the identifier of the program to test (end with ctrl+z): "<<endl;
} //delete [] unsortedArray;
} int main()
{
TestSortDriver(); return ;
}