排序算法总结

时间：2024.4.27

一、插入排序(Insertion Sort)

1. 基本思想：

每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

2. 排序过程：

【示例】：

[初始关键字] [49] 38 65 97 76 13 27 49

J=2(38) [38 49] 65 97 76 13 27 49

J=3(65) [38 49 65] 97 76 13 27 49

J=4(97) [38 49 65 97] 76 13 27 49

J=5(76) [38 49 65 76 97] 13 27 49

J=6(13) [13 38 49 65 76 97] 27 49

J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97]

复制内容到剪贴板

排序算法总结

Procedure InsertSort(Var R : FileType);

//对R[1..N]按递增序进行插入排序, R[0]是监视哨//

Begin

for I := 2 To N Do //依次插入R[2],...,R[n]//

begin

R[0] := R; J := I - 1;

While R[0] < R[J] Do //查找R的插入位置//

begin

R[J+1] := R[J]; //将大于R的元素后移//

J := J - 1

end

R[J + 1] := R[0] ; //插入R //

end

End; //InsertSort //

二、选择排序

1. 基本思想：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2. 排序过程：

【示例】：

初始关键字 [49 38 65 97 76 13 27 49]

第一趟排序后 13 ［38 65 97 76 49 27 49]

第二趟排序后 13 27 ［65 97 76 49 38 49]

第三趟排序后 13 27 38 [97 76 49 65 49]

第四趟排序后 13 27 38 49 [49 97 65 76]

第五趟排序后 13 27 38 49 49 [97 97 76]

第六趟排序后 13 27 38 49 49 76 [76 97]

第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97

复制内容到剪贴板

排序算法总结

Procedure SelectSort(Var R : FileType); //对R[1..N]进行直接选择排序 // Begin

for I := 1 To N - 1 Do //做N - 1趟选择排序//

begin

K := I;

For J := I + 1 To N Do //在当前无序区R[I..N]中选最小的元素R[K]// begin

If R[J] < R[K] Then K := J

end;

If K <> I Then //交换R和R[K] //

begin Temp := R; R := R[K]; R[K] := Temp; end;

end

End; //SelectSort //

三、冒泡排序(BubbleSort)

1. 基本思想：

两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

2. 排序过程：

设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。

【示例】：

49 13 13 13 13 13 13 13

38 49 27 27 27 27 27 27

65 38 49 38 38 38 38 38

97 65 38 49 49 49 49 49

76 97 65 49 49 49 49 49

13 76 97 65 65 65 65 65

27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97

复制内容到剪贴板

排序算法总结

Procedure BubbleSort(Var R : FileType) //从下往上扫描的起泡排序// Begin

For I := 1 To N-1 Do //做N-1趟排序//

begin

NoSwap := True; //置未排序的标志//

For J := N - 1 DownTo 1 Do //从底部往上扫描//

begin

If R[J+1]< R[J] Then //交换元素//

begin

Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp;

NoSwap := False

end;

If NoSwap Then Return//本趟排序中未发生交换，则终止算法//

end

End; //BubbleSort//

四、快速排序（Quick Sort）

1. 基本思想：

在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均

已排序为止。

2. 排序过程：

【示例】：

初始关键字 [49 38 65 97 76 13 27 49］

第一次交换后

［27 38 65 97 76 13 49 49］

第二次交换后

［27 38 49 97 76 13 65 49］

J向左扫描，位置不变，第三次交换后

［27 38 13 97 76 49 65 49］

I向右扫描，位置不变，第四次交换后

［27 38 13 49 76 97 65 49］

J向左扫描

［27 38 13 49 76 97 65 49］

（一次划分过程）

初始关键字

［49 38 65 97 76 13 27 49］

一趟排序之后

［27 38 13］ 49 ［76 97 65 49］

二趟排序之后

［13］ 27 ［38］ 49 ［49 65］76 ［97］

三趟排序之后 13 27 38 49 49 ［65］76 97

最后的排序结果 13 27 38 49 49 65 76 97 各趟排序之后的状态

复制内容到剪贴板

排序算法总结

Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer); //对无序区R[1,H]做划分，I给以出本次划分后已被定位的基准元素的位置 // Begin

I := 1; J := H; X := R ;//初始化，X为基准//

Repeat

While (R[J] >= X) And (I < J) Do

begin

J := J - 1 //从右向左扫描，查找第1个小于 X的元素//

If I < J Then //已找到R[J] 〈X//

begin

R := R[J]; //

排序算法总结

相当于交换R和R[J]//

I := I + 1

end;

While (R <= X) And (I < J) Do

I := I + 1 //从左向右扫描，查找第1个大于 X的元素///

end;

If I < J Then //已找到R > X //

begin R[J] := R; //相当于交换R和R[J]//

J := J - 1

end Until I = J;

R := X //基准X已被最终定位//

End; //Parttion //

复制内容到剪贴板

Procedure QuickSort(Var R :FileType; S,T: Integer); //对R[S..T]快速排序//

Begin

If S < T Then //当R[S..T]为空或只有一个元素是无需排序//

begin

Partion(R, S, T, I); //对R[S..T]做划分//

QuickSort(R, S, I-1);//递归处理左区间R[S,I-1]//

QuickSort(R, I+1,T);//递归处理右区间R[I+1..T] //

end;

End; //QuickSort//

五、堆排序(Heap Sort)

1. 基本思想：

堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

2. 堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性： Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。

3. 排序过程：

堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。【示例】：对关键字序列42，13，91，23，24，16，05，88建堆

排序算法总结

复制内容到剪贴板

Procedure Sift(Var R :FileType; I, M : Integer);

//在数组R[I..M]中调用R，使得以它为完全二叉树构成堆。事先已知其左、右子树(2I+1 <=M时)均是堆//

Begin

X := R; J := 2*I; //若J <=M, R[J]是R的左孩子//

While J <= M Do //若当前被调整结点R有左孩子R[J]//

begin

If (J < M) And R[J].Key < R[J+1].Key Then

J := J + 1 //令J指向关键字较大的右孩子//

//J指向R的左、右孩子中关键字较大者//

If X.Key < R[J].Key Then //孩子结点关键字较大//

begin

R := R[J]; //将R[J]换到双亲位置上//

I := J ; J := 2*I //继续以R[J]为当前被调整结点往下层调整// end;

Else

Exit//调整完毕，退出循环//

end

R := X;//将最初被调整的结点放入正确位置//

End;//Sift//

复制内容到剪贴板

排序算法总结

Procedure HeapSort(Var R : FileType); //对R[1..N]进行堆排序// Begin

For I := N Div Downto 1 Do //建立初始堆//

Sift(R, I , N)

For I := N Downto 2 do //进行N-1趟排序//

begin

T := R[1]; R[1] := R; R := T;//将当前堆顶记录和堆中最后一个记录交换//

Sift(R, 1, I-1) //将R[1..I-1]重成堆//

end

End; //HeapSort//

六、几种排序算法的比较和选择

1. 选取排序方法需要考虑的因素：

(1) 待排序的元素数目n；

(2) 元素本身信息量的大小；

(3) 关键字的结构及其分布情况；

(4) 语言工具的条件，辅助空间的大小等。

2. 小结：

(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。

(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序法中被认为是最好的方法。

(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。

这句话很重要它告诉我们自己写的算法是有改进到最优当然没有必要一直追求最优

(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。

第二篇：C++排序算法总结及性能大致分析

这里讲的排序默认为内排序。

参考书籍：数据结构(C语言版)

秦玉平马靖善主编

冯佳昕周连秋副主编

清华大学出版社

按照排序过程中依据的原则不同划分为：

（1）插入排序包括直接插入排序，折半插入排序，2_路插入排序，shell排序

（2）交换排序包括简单交换排序，冒泡排序，快速排序

（3）选择排序包括简单选择排序，*树形选择排序，*堆排序

（4）归并排序

（5）计数排序包括*计数排序，基数排序

*上面打星号的代码没有添加*

下面代码修改自/%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/5ad1f372177b21158701b093.html

主要修改了快速排序的错误，添加了折半插入排序和2_路插入排序，而且按照以上(1)~(5)重新改写了程序的结构。

代码如下：

排序头文件：sort.h

#ifndef __SORT_H__

#define __SORT_H__

/************************************************************************/

/* 排序头文件 */

/************************************************************************/

/* 头文件包含 */

#include "insertSort.h"

#include "exchangeSort.h"

#include "selectSort.h"

#include "mergeSort.h"

#include "countSort.h"

/********************************************************************

****/

#endif

（1）插入排序：insertSort.h

#ifndef __INSERTSORT_H__

#define __INSERTSORT_H__

/************************************************************************/

/*常用头文件包含*/

#include <vector>

using namespace std;

/************************************************************************/

/*插入排序的思想

插入排序属于插入方法的排序算法，它的想法是从第一个元素开始，创建有序序列，把未排序序列依次插入到有序序列中，以此类推

/************************************************************************/

/*函数实现，按从小到大排序*/

template <class T>

void insertSort(vector<T>& v)

{

/*直接插入排序*/

for (unsigned int i = 1; i < v.size(); i++)

{

T tmp = v[i];

int j = i - 1;

while (j >= 0 && v[j] > tmp)

{

v[j+1] = v[j];

j--;

}

v[j+1] = tmp;

}

template <class T>

void biInsertSort(vector<T>& v)

{

/*折半插入排序*/

for (unsigned int i = 1; i < v.size(); i++) {

T tmp = v[i];

int low = 0;

int high = i - 1;

while (low <= high)

{

int mid = (low + high) / 2;

if (tmp > v[mid])

{

low = mid + 1;

}

else

{

high = mid - 1;

}

int j = i - 1;

while (j >= 0 && v[j] > tmp)

{

v[j+1] = v[j];

j--;

}

v[j+1] = tmp;

}

template <class T>

void binInsertSort(vector<T>& v)

{

/*2_路查找排序*/

vector<T> vecTmp(v);

int first,final,low,high,mid,k,j; unsigned int i,siz;

siz = v.size();

first = final = 0;

for (i = 1; i < siz; i++)

{

T tmp = v[i];

if (tmp >= vecTmp[0])

{

low = 0;

high = final;

while (low <= high)

{

mid = (low + high) / 2; if (v[i] > vecTmp[mid]) {

low = mid + 1;

}

else

{

high = mid - 1;

}

for (j = final; j >= low; j--) {

vecTmp[j+1] = vecTmp[j]; }

vecTmp[low] = tmp;

final++;

}

else

{

if (first == 0)

{

first = siz - 1;

vecTmp[siz-1] = tmp; }

else

{

low = first;

high = siz - 1;

while (low <= high)

{

mid = (low + high) / 2; if (tmp > vecTmp[mid]) {

low = mid + 1;

}

else

{

high = mid - 1;

}

for (j = first; j <= high; j++)

{

vecTmp[j-1] = vecTmp[j];

}

vecTmp[high] = tmp;

first--;

}

for (i = 0,j = first; j < siz; i++,j++)

{

v[i] = vecTmp[j];

}

for (k = 0; k <= final; k++)

{

v[i++] = vecTmp[k];

}

/************************************************************************/

/* 希尔排序 */

/*希尔排序的思想

希尔排序属于插入方法的排序算法，可以说是插入排序算法的改进版本，它的想法是把数据分组，在分组内进行插入排序，以此类推，分组的大小跟数据量有关系，D. E. Knuth建议数据量很大时按3*n+1分组，例如100 的数据时，可以取1，4，13，40。

template <class T>

void shellSort(vector<T>& v)

{

for (unsigned int count = (unsigned int)v.size()/2; count > 0; count /= 2)

{

for(unsigned int group = 0; group < count; group++)

{

for (unsigned int i = group; i < v.size(); i += count)

{

T tmp = v[i];

int j = i - count;

while (j >=0 && v[j] > tmp)

{

v[j+count] = v[j];

j -= count;

}

v[j+count] = tmp;

}

/************************************************************************/

#endif

（2）交换排序：exchangeSort.h

#ifndef __EXCHANGESORT_H__

#define __EXCHANGESORT_H__

/************************************************************************/

/*常用头文件包含*/

#include <algorithm>

/*要用template<class Type> void swap(Type& _Left,Type& _Right);*/ #include <vector>

#include <math.h>

using namespace std;

/************************************************************************/

/*交换排序的思想

交换排序属于比较法的排序算法，它的想法是扫描整个数据，从第0个元素开始，跟以后的元素逐个比较，按照排序规则(从小到大或者从大到小)交换顺序，比较完第a后再去比较第a+1个元素，以此类推

/*函数实现，按从小到大排序*/

template <class T>

void exchageSort(vector<T>& v)

{

for (unsigned int i = 0; i < v.size()-1; i++)

{

for (unsigned int j = i + 1; j < v.size(); j++)

{

if (v[i]>v[j])

{

swap(v[i],v[j]);

}

/************************************************************************/

/*冒泡排序的思想

冒泡排序属于比较法的排序算法，它的想法是比较相邻的两个数据，按照排序规则(从小到大或者从大到小)交换顺序，再去比较下一组相邻元素，以此类推 */

/************************************************************************/

/*函数实现，按从小到大排序*/

template <class T>

void bubbleSort(vector<T>& v)

{

bool flag = true;

for (unsigned int i = 0; (i < v.size()-1) && (flag); i++)

{

flag = false;

for (unsigned int j = 0; j < v.size() - i - 1; j++)

{

if (v[j]>v[j+1])

{

swap(v[j],v[j+1]);

flag = true;

}

/************************************************************************/

/*快速排序的思想

快速排序的想法是尽可能的减少每次排序的数据量以提高效率，那么对于任意从数据中取出的数据，可以按照大小把比它小的放在它的左边，比它大的放在它的右边，那么这个数的位置就确定了，再在它的左右两边分别按此排序，这就是快速排序。

/*函数实现，按从小到大排序*/

template <class T>

void quickSort(vector<T>& v,unsigned int left, unsigned int right) {

if (left < right)

{

unsigned int pivot = left;

unsigned int low = left + 1;

unsigned int high = right;

while (low < high)

{

while(low < high && v[low] <= v[pivot])

{

low++;

}

while(low < high && v[high] >= v[pivot])

{

high--;

}

if (low < high)

{

swap(v[low],v[high]);

}

if (v[pivot] > v[high])

{

swap(v[pivot],v[high]);

}

if (high > left)

{

quickSort(v,left,high-1);

}

if (low < right)

{

quickSort(v,low,right);

}

/************************************************************************/

#endif

（3）选择排序：selectSort.h

#ifndef __SELECTSORT_H__

#define __SELECTSORT_H__

/************************************************************************/

/*常用头文件包含*/

#include <algorithm>

/*要用template<class Type> void swap(Type& _Left,Type& _Right);*/ #include <vector>

using namespace std;

/************************************************************************/

/*选择排序的思想

选择排序属于选择法的排序算法，它的想法是按照排序规则(从小到大或者从大到小)查找最小(大)的元素，并与第一个元素交换，再在剩下的元素中重复此过程以此类推

/************************************************************************/

/*函数实现，按从小到大排序*/

template <class T>

void selectSort(vector<T>& v)

{

for (unsigned int i = 0; i < v.size()-1; i++)

{

unsigned int min = i;

for (unsigned int j = i + 1; j < v.size(); j++)

{

if (v[min]>v[j])

{

min = j;

}

swap(v[i],v[min]);

}

//////////////////////////////////////////////////////////////////////////

#endif

（4）归并排序：mergeSort.h

#ifndef __MERGESORT_H__

#define __MERGESORT_H__

/************************************************************************/

/*常用头文件包含*/

#include <algorithm>

/*要用template<class Type> void swap(Type& _Left,Type& _Right);*/ #include <vector>

using namespace std;

/************************************************************************/

/*归并排序的思想

归并排序的思想跟快排序类似，即先不断地把数据分割至每组只有一个数据，然后在按大小归并成一组有序数。

/*函数实现，按从小到大排序*/

template <class T>

void mergeSort(vector<T>& v,unsigned int left, unsigned int right) {

unsigned int half;

if (left < right)

{

half = (left + right) / 2;

mergeSort(v,left,half);

mergeSort(v,half + 1,right);

merge(v,left,v,left,half,v,half+1,right);

}

template <class T>

void merge(vector<T>&v, unsigned int left,

vector <T>A, unsigned int leftA, unsigned int rightA, vector <T>B, unsigned int leftB, unsigned int rightB) {

//归并，把向量A按始末位置leftA，rightA，

// 向量B按始末位置leftB，rightB ,

// 排序归并到v中

unsigned int indexA = leftA;

unsigned int indexB = leftB;

while (indexA <= rightA && indexB <= rightB)

{

if (A[indexA] > B[indexB])

{

v[left++] = B[indexB++];

}

else

{

v[left++] = A[indexA++];

}

while (indexA <= rightA)

{

v[left++] = A[indexA++];

}

while (indexB <= rightB)

{

v[left++] = B[indexB++];

}

/************************************************************************/

#endif

（5）计数排序：countSort.h

#ifndef __COUNTSORT_H__

#define __COUNTSORT_H__

/************************************************************************/

/*常用头文件包含*/

#include <vector>

#include <math.h>

using namespace std;

/************************************************************************/

/*基数排序的思想

基数排序是根据数字的性质来进行的排序算法，它首先分离出个位数，并把原数据按照个位数大小依次排序，得到一个排序结果，再将这个排序结果按照十位数的大小在进行排序，以此类推，知道最高位排序即完成。

基数排序必须是正整数。

/*函数实现，按从小到大排序*/

unsigned int findMax(vector<unsigned int> v);

unsigned int findk(unsigned int num,unsigned int kth);

void radixSort(vector<unsigned int>& v)

{

unsigned int no;

unsigned int count = findMax(v);

vector<vector<unsigned int>> vTmp (10,vector<unsigned int>(v.size())); for (unsigned int i = 1; i <= count; i++)

{

int noCount[10] = {0};

for (unsigned int j = 0; j < v.size(); j++)

{

no = findk(v[j],i);

vTmp[no][noCount[no]] = v[j];

noCount[no]++;

}

int index = 0;

for (int i = 0; i < 10; i++)

{

for (int k = 0; k < noCount[i]; k++)

{

v[index++] = vTmp[i][k];

}

unsigned int findMax(vector<unsigned int> v)

{

//函数查找最大数的位数

unsigned int maxx = v[0];

for (unsigned int i = 1; i < v.size(); i++)

{

if (maxx < v[i])

{

maxx = v[i];

}

return (unsigned int)log10((float)maxx) + 1;

}

unsigned int findk(unsigned int num,unsigned int kth)

{

//函数查找正整数的第k位上的数字 kth = 1,2,3,...个位，十位，百位 int m = 1;

for (unsigned int i = 1; i <= kth; i++)

{

m *= 10;

}

return (num * 10 / m) % 10;

}

/************************************************************************/

#endif

测试代码：test.h

#include "sort.h"

#include "timer.h"

#include "randomNumber.h"

#include <iostream>

#include <fstream>

using namespace std;

const int SIZ = 10000;

const int MAX = 10*SIZ;

const int TESTTIME = 20;

int main()

{

vector<vector<long> >aver(10,vector<long>(TESTTIME)); vector<long> averTime(10);

ofstream out("c:\\averageTime.txt");

for (int i = 0; i < TESTTIME; i++)

{

cout << "这是第" << i+1 << "次测试！" << endl; out << "这是第" << i+1 << "次测试！" << endl; timer t0,t1,t2,t3,t4,t5,t6,t7,t8,t9;

vector<unsigned int> v;

randomNumber rnd;

for (int j = 0; j < SIZ; j++)

{

v.push_back(rnd.random(MAX));

}

vector<unsigned int> v0(v);

vector<unsigned int> v1(v);

vector<unsigned int> v2(v);

vector<unsigned int> v3(v);

vector<unsigned int> v4(v);

vector<unsigned int> v5(v);

vector<unsigned int> v6(v);

vector<unsigned int> v7(v);

vector<unsigned int> v8(v);

vector<unsigned int> v9(v);

t0.start();

insertSort(v0);

t0.stop();

aver[0][i] += t0.timeElapse();

out << "insertSort:" << aver[0][i] << endl; cout << "***insertSort over***" << endl; t1.start();

biInsertSort(v1);

t1.stop();

aver[1][i] += t1.timeElapse();

out << "biInsertSort:" << aver[1][i] << endl; cout << "***biInsertSort over***" << endl;

t2.start();

binInsertSort(v2);

t2.stop();

aver[2][i] += t2.timeElapse();

out << "binInsertSort:" << aver[2][i] << endl; cout << "***binInsertSort over***" << endl;

t3.start();

shellSort(v3);

t3.stop();

aver[3][i] += t3.timeElapse();

out << "shellSort:" << aver[3][i] << endl; cout << "***shellSort over***" << endl; t4.start();

exchageSort(v4);

t4.stop();

aver[4][i] += t4.timeElapse();

out << "exchageSort:" << aver[4][i] << endl; cout << "***exchageSort over***" << endl;

t5.start();

bubbleSort(v5);

t5.stop();

aver[5][i] += t5.timeElapse();

out << "bubbleSort:" << aver[5][i] << endl; cout << "***bubbleSort over***" << endl;

t6.start();

quickSort(v6,0,v6.size()-1);

t6.stop();

aver[6][i] += t6.timeElapse();

out << "quickSort:" << aver[6][i] << endl; cout << "***quickSort over***" << endl;

t7.start();

selectSort(v7);

t7.stop();

aver[7][i] += t7.timeElapse();

out << "selectSort:" << aver[7][i] << endl; cout << "***selectSort over***" << endl;

t8.start();

mergeSort(v8,0,v8.size()-1);

t8.stop();

aver[8][i] += t8.timeElapse();

out << "mergeSort:" << aver[8][i] << endl; cout << "***mergeSort over***" << endl;

t9.start();

radixSort(v9);

t9.stop();

aver[9][i] += t9.timeElapse();

out << "radixSort:" << aver[9][i] << endl; cout << "***radixSort over***" << endl; }

for (int j = 0; j < 10; j++)

{

for (int k = 0; k < TESTTIME; k++) {

out << aver[j][k] << " ";

}

out << endl;

}

for (int j = 0; j < 10; j++)

{

for (int k = 0; k < TESTTIME; k++) {

averTime[j] += aver[j][k];

}

averTime[j] /= TESTTIME;

out << averTime[j] << endl;

}

out.close();

return 0;

}

计时器代码以及随机数产生代码请分别参阅： /%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/a0421781846ea8de9123d9fa.html /%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/d3f21efca0061f4cd6887d28.html

程序运行结果：

这是第1次测试！

insertSort:8063

biInsertSort:8109

binInsertSort:4828

shellSort:94

exchageSort:18468

bubbleSort:18672

quickSort:63

selectSort:12593

mergeSort:641

radixSort:63

这是第2次测试！

insertSort:8031

biInsertSort:8110

binInsertSort:4859

shellSort:94

exchageSort:18469

bubbleSort:18703

quickSort:62

selectSort:12531

mergeSort:625

radixSort:63

这是第3次测试！

insertSort:8062

biInsertSort:8141

binInsertSort:2719

shellSort:94

exchageSort:18546

bubbleSort:18813

quickSort:78 selectSort:12625 mergeSort:641 radixSort:47 这是第4次测试！ insertSort:8047 biInsertSort:8109 binInsertSort:5328 shellSort:94

exchageSort:18531 bubbleSort:18735 quickSort:63 selectSort:12562 mergeSort:641 radixSort:62 这是第5次测试！ insertSort:8062 biInsertSort:8125 binInsertSort:4625 shellSort:94

exchageSort:18641 bubbleSort:18781 quickSort:78 selectSort:12594 mergeSort:640 radixSort:47 这是第6次测试！ insertSort:8093 biInsertSort:8172 binInsertSort:3078 shellSort:93

exchageSort:18563 bubbleSort:18829 quickSort:78 selectSort:13468 mergeSort:688 radixSort:47 这是第7次测试！ insertSort:8797 biInsertSort:8671 binInsertSort:2813 shellSort:93

exchageSort:19094 bubbleSort:19578

quickSort:78 selectSort:13156 mergeSort:656 radixSort:63 这是第8次测试！ insertSort:8313 biInsertSort:8422 binInsertSort:4125 shellSort:109 exchageSort:19125 bubbleSort:19328 quickSort:63 selectSort:13188 mergeSort:672 radixSort:62 这是第9次测试！ insertSort:8266 biInsertSort:8391 binInsertSort:3937 shellSort:94

exchageSort:19141 bubbleSort:18703 quickSort:78 selectSort:12562 mergeSort:657 radixSort:46

这是第10次测试！ insertSort:8312 biInsertSort:8360 binInsertSort:3500 shellSort:94

exchageSort:19187 bubbleSort:19484 quickSort:62 selectSort:13266 mergeSort:703 radixSort:62

这是第11次测试！ insertSort:8313 biInsertSort:8500 binInsertSort:3593 shellSort:94

exchageSort:19015 bubbleSort:19078

quickSort:79 selectSort:13047 mergeSort:656 radixSort:47

这是第12次测试！ insertSort:8422 biInsertSort:8375 binInsertSort:2813 shellSort:109 exchageSort:18906 bubbleSort:19094 quickSort:63 selectSort:12656 mergeSort:641 radixSort:47

这是第13次测试！ insertSort:8016 biInsertSort:8109 binInsertSort:4360 shellSort:78

exchageSort:18266 bubbleSort:18547 quickSort:63 selectSort:12750 mergeSort:640 radixSort:47

这是第14次测试！ insertSort:8000 biInsertSort:8109 binInsertSort:2953 shellSort:94

exchageSort:18438 bubbleSort:18562 quickSort:63 selectSort:12547 mergeSort:641 radixSort:47

这是第15次测试！ insertSort:7906 biInsertSort:8078 binInsertSort:3547 shellSort:94

exchageSort:18391 bubbleSort:18656

quickSort:78 selectSort:12687 mergeSort:656 radixSort:47

这是第16次测试！ insertSort:7953 biInsertSort:8094 binInsertSort:5000 shellSort:94

exchageSort:19015 bubbleSort:18954 quickSort:63 selectSort:13063 mergeSort:656 radixSort:63

这是第17次测试！ insertSort:8266 biInsertSort:8344 binInsertSort:3453 shellSort:93

exchageSort:18844 bubbleSort:18938 quickSort:62 selectSort:12828 mergeSort:640 radixSort:47

这是第18次测试！ insertSort:8156 biInsertSort:8344 binInsertSort:4500 shellSort:109 exchageSort:19000 bubbleSort:19110 quickSort:78 selectSort:12859 mergeSort:625 radixSort:63

这是第19次测试！ insertSort:8203 biInsertSort:8437 binInsertSort:3188 shellSort:94

exchageSort:19046 bubbleSort:19391

quickSort:78

selectSort:12781

mergeSort:625

radixSort:47

这是第20次测试！

insertSort:7984

biInsertSort:8125

binInsertSort:3391

shellSort:94

exchageSort:18765

bubbleSort:18922

quickSort:78

selectSort:13031

mergeSort:641

radixSort:62

8063 8031 8062 8047 8062 8093 8797 8313 8266 8312 8313 8422 8016 8000 7906 7953 8266 8156 8203 7984

8109 8110 8141 8109 8125 8172 8671 8422 8391 8360 8500 8375 8109 8109 8078 8094 8344 8344 8437 8125

4828 4859 2719 5328 4625 3078 2813 4125 3937 3500 3593 2813 4360 2953 3547 5000 3453 4500 3188 3391

94 94 94 94 94 93 93 109 94 94 94 109 78 94 94 94 93 109 94 94

18468 18469 18546 18531 18641 18563 19094 19125 19141 19187 19015 18906 18266 18438 18391 19015 18844 19000 19046 18765

18672 18703 18813 18735 18781 18829 19578 19328 18703 19484 19078 19094 18547 18562 18656 18954 18938 19110 19391 18922

63 62 78 63 78 78 78 63 78 62 79 63 63 63 78 63 62 78 78 78

12593 12531 12625 12562 12594 13468 13156 13188 12562 13266 13047 12656 12750 12547 12687 13063 12828 12859 12781 13031

641 625 641 641 640 688 656 672 657 703 656 641 640 641 656 656 640 625 625 641

63 63 47 62 47 47 63 62 46 62 47 47 47 47 47 63 47 63 47 62 8163

8256

3830

18772

18943

12839

649

（以上结果单位为ms）

由于函数里面调用了泛型算法，以上结果只是作为参照。下面以图形的结果做了比较：

插入排序比较：

C排序算法总结及性能大致分析

交换排序比较：

C排序算法总结及性能大致分析

改进排序比较：

C排序算法总结及性能大致分析

简单排序比较：

C排序算法总结及性能大致分析

下面给出常用排序算法的性能比较（抄自数据结构(C语言版)，excel编辑）：

C排序算法总结及性能大致分析

转载请注明来自：/秀才太守

本文网址：/%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/87e17c45dce84088b3b7dc40.html

更多相关推荐：

c语言排序算法总结: 排序算法总结选择法排序：for(i=0;i9;i++){max=i;for(j=i+1;j10;j++)if(a[max]a[j])max=j;/*max为查找范围最大数所在元素下标*/if(max!=i)（i…
c语言排序算法总结(主要是代码实现): 冒泡排序（BubbleSort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。…
排序算法总结: 按平均时间将排序分为四类：（1）平方阶(O(n2))排序一般称为简单排序，例如直接插入、直接选择和冒泡排序；（2）线性对数阶(O(nlgn))排序如快速、堆和归并排序；（3）O(n1+￡)阶排序￡是介于0和1之…
计算机考研数据结构查找和排序算法总结: 查找算法总结静态查找n1顺序表的查找-顺序查找：查找成功时的平均查找长度ASL=n?n?i?1=i?1(n?1)2,查找不成功时的比较次数为n+1,故查找成功与不成功等概率时的平均查找长度为12n?(n?i?1…
八大排序算法总结: 八大排序算法总结插入排序1.直接插入排序原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。要点：设立哨兵，作为临时存储和判…
排序算法总结: 现有序列{9,3,5,1,6,2,8,4,7}，以此为例子，阐述各个常用排序算法。直接插入排序：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大…
用php实现的各种排序算法总结: 用php实现的各种排序算法总结优化php性能的五个实用技巧：以下是五个优化技巧，熟练掌握后对于开发还是很有帮助的。1.对字符串使用单引号PHP引擎允许使用单引号和双引号来封装字符串变量，但是这个是有很大的差别的…

排序算法总结: 所谓排序就是要整理文件中的记录使之按关键字递增或递减次序排列起来当待排序记录的关键字都不相同时排序结果是惟一的否则排序结果不惟一在待排序的文件中若存在多个关键字相同的记录经过排序后这些具有相同关键字的记录之间的...
排序算法总结: 一插入排序InsertionSort1基本思想每次将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置使数列依然有序直到待排序数据元素全部插入完为止2排序过程示例初始关键字493865977613274...
排序算法总结: 3排序算法总结31直接插入排序顺序遍历元素并将其插入到其之前已经有序的数组中在最好情况下即已经全部按所需的次序排列好则比对次数仅为n1记录无需移动时间复杂度为On1在最坏情况下即已经全部按所需的次序反序排列好则...
排序算法总结: 排序算法总结一插入排序InsertionSort1基本思想每次将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置使数列依然有序直到待排序数据元素全部插入完为止2排序过程示例初始关键字493865977...
10种排序算法总结: 10种排序算法总结排序算法有很多所以在特定情景中使用哪一种算法很重要为了选择合适的算法可以按照建议的顺序考虑以下标准1执行时间2存储空间3编程工作对于数据量较小的情形12差别不大主要考虑3而对于数据量大的1为首...

热门关注