第四十六讲 排序算法(1)

 

 

 

 

 

昨天给大家的数组排序问题其实是想要把大家带入STL是,但是看到大家纷纷回答我觉得有必要来说说关于排序的问题。
 

 

 

 

 

从大家的回答中,看得出大家的数据结构功底不错,不过我很好奇的是很多选择了冒泡排序,不过想想也不足为奇,冒泡排序简单易懂,而且大家可能面临的数据都不大,所以冒泡排序对性能的影响也还是可以接受的了,其中只有一位同学回答说用STL的算法,当然,这个答案很好的啦,对你个人来使确实不错,不过,我当时提出这个问题的真正用意就是要通过他带大家进入STL,所以STL的算法我们这里不作讨论,其中也有人回答用快速排序,还有回答说希尔排序,足见大家对算法还是挺有了解的,可能比我懂的还要多(话说算法这块,我还真没有吃透的了,就好比我会对这图论发呆)。
 

 

 

既然提起了大家对排序的兴趣,我们不妨来看看排序有哪些算法,也算是为我们学习STL热下身啦。
 

 

 

最一般的排序方法当然就是冒泡排序法了,这个实现极为简单:
——————————–
template<typename T>
 

 

 

 

 

 

 

void My_Sort(vector<T>&

a)
 

 

 

 

 

 

{
 

 

 

 

 

 

 

 

 

 

 

 

 

 

int i,j;


 

 

 

 

 

 

 

 

 

 

 

 

 

 

for(i=0;

i<a.size();

i++)
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

for(j=i;

j<a.size();

j++)
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

{
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

}
 

 

 

 

 

 

 

}
———————————
 

 

 

 

正因这个算法简单,所以使用他得付出牺牲性能的代价,为什么这么说呢?待会我会给出一个测试程序,大家就会清楚了,事实上,我们上面的冒泡实现还是用了STL的一部分算法(swap),如果不是使用STL的这部分算法的话,会更吓人。
 

 

 

当然,再一般的会选择插入排序法,这个算法的性能大约是冒泡的三倍,尤其是数据量不大的时候更是可见一斑,插入排序的实现方案看起来像下面这样:
———————————
template<typename T>
 

 

 

 

 

 

void insertionsort(vector<T>&

a)
 

 

 

{
 

 

 

 

 

 

int k;


 

 

 

 

 

 

for(int p=0;

p<a.size();

p++)
 

 

 

 

 

 

{
 

 

 

 

 

 

 

 

 

T
temp = a[p];


 

 

 

 

 

 

 

 

 

for(k=p;

k>0&

&

temp<a[k-1];

k–)
 

 

 

 

 

 

 

 

 

 

 

 

a[k]=a[k-1];


 

 

 

 

 

 

 

 

 

a[k]=temp;


 

 

 

 

 

 

}
 

 

 

}
 

 

 

 


————————————-
 

 

 

谢尔排序曾一度认为是最好的算法,不过后来证明了他其实还是存在亚二次的,不过不管怎么说,这个算法确实也是不错的选择的了,谢尔排序就是一段段的对比,直到最后单一元素对比,所以他实现看起来应该像下面这样:
———————————–
template<typename T>
 

 

 

 

 

 

void shellsort(vector<T>&

a)
 

 

 

{
 

 

 

 

 

 

for(int gap=a.size()/2;

gap>0;

gap /= 2)
 

 

 

 

 

 

{
 

 

 

 

 

 

 

 

 

for(int i=gap;

i<a.size();

i++)
 

 

 

 

 

 

 

 

 

{
 

 

 

 

 

 

 

 

 

 

 

 

T
temp = a[i];


 

 

 

 

 

 

 

 

 

 

 

 

int j=i;


 

 

 

 

 

 

 

 

 

 

 

 

for(j;

j>=gap&

&

temp<=a[j-gap];

j -= gap)
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a[j] = a[j-gap];


 

 

 

 

 

 

 

 

 

 

 

 

a[j]=temp;


 

 

 

 

 

 

 

 

 

}
 

 

 

 

 

 

}
 

 

 

}
————————————-
 

 

他的实现和冒泡相差不多,但是性能却千差万别,从我们的实现代码中可以看出,谢尔排序是一半半的对比,将小的元素往前段扔,大的就往后扔。
 

 

并归排序的性能又要比谢尔排序好上一些,将近一倍,这个算法基本的操作是合并两个已经排好序的数组,所以这个实现的关键处是递归:
———————————
template<typename T>
 

 

 

 

 

 

void mergesort(vector<T>&

a)
 

 

 

{
 

 

 

 

 

 

vector<T>tempA(a.size());


 

 

 

 

 

 

mergesort(a,tempA,0,a.size()-1);


 

 

 

}
 

 

 


 

 

 

template<typename T>
 

 

 

 

 

 

void mergesort(vector<T>&

a,vector<T>&

tempA,int left,int right)
 

 

 

{
 

 

 

 

 

 

if(left<right)
 

 

 

 

 

 

{
 

 

 

 

 

 

 

 

 

int center = (left + right)/2;


 

 

 

 

 

 

 

 

 

mergesort(a,tempA,left,center);


 

 

 

 

 

 

 

 

 

mergesort(a,tempA,center+1,right);


 

 

 

 

 

 

 

 

 

merge(a,tempA,left,center+1,right);


 

 

 

 

 

 

}
 

 

 

}
 

 

 


 

 

 

template<typename T>
 

 

 

 

 

 

void merge(vector<T>&

a,vector<T>&

b,int left,int center,int right)
 

 

 

{
 

 

 

 

 

 

int leftend = center-1;


 

 

 

 

 

 

int temppos = left;


 

 

 

 

 

 

int numelement = right – left + 1;


 

 

 

 

 

 

while(left<leftend &

&

center<right)
 

 

 

 

 

 

 

 

 

if(a[left]<a[center])
 

 

 

 

 

 

 

 

 

 

 

 

b[temppos++]=a[left++];


 

 

 

 

 

 

 

 

 

else
 

 

 

 

 

 

 

 

 

 

 

 

b[temppos++]=a[center++];


 

 

 

 

 

 

 

 

 

while(left<leftend)
 

 

 

 

 

 

 

 

 

 

 

 

b[temppos++] = a[left++];


 

 

 

 

 

 

 

 

 

while(center<right)
 

 

 

 

 

 

 

 

 

 

 

 

b[temppos++] = a[center++];


 

 

 

 

 

 

 

 

 

for(int i=0;

i<numelement;

i++,right–)
 

 

 

 

 

 

 

 

 

 

 

 

a[right] = b[right];


 

 

 

}
—————————
 

 

 

 

最后,关于快速排序和堆排序就留待明天再说,下面我们来测试一下这几个排序算法的性能:
—————————-
//test.cpp
#include <ctime>
#include <algorithm>
#include "

MySort.h"


using namespace My_Code;

int main()
{
 

 

 

long diffTime,StartTime,EndTime;


 

 

 

vector<int>test;


 

 

 

for(int i=0;

i<40000;

i++)
 

 

 

{
 

 

 

 

 

 

int
temp = rand();


 

 

 

 

 

 

test.push_back(temp);


 

 

 

}
 

 

 

vector<int>::iterator it=test.begin();


/* 

 

 

while(it != test.end())
 

 

 

{
 

 

 

 

 

 

cout<<*it<<endl;


 

 

 

 

 

 

it++;


 

 

 

}
 

 

 

cout<<"

———————————"

<<endl;

*/
 

 

 

it = test.begin();


 

 

 

StartTime = clock();


// 

 

 

My_Sort(test);

//131165Ms
// 

 

 

sort(test.begin(),test.end());

//17Ms
// 

 

 

insertionsort(test);

//49569Ms
// 

 

 

shellsort(test);

//203Ms
// 

 

 

mergesort(test);

//125Ms
// 

 

 

heapsort(test);

//156Ms
 

 

 

EndTime = clock();


 

 

 

diffTime = EndTime – StartTime;


/* 

 

 

while(it != test.end())
 

 

 

{
 

 

 

 

 

 

cout<<*it<<endl;


 

 

 

 

 

 

it++;


 

 

 

}*/
 

 

 

cout<<"

—————————–"

<<endl;


 

 

 

cout<<diffTime<<"

Ms"

<<endl;


 

 

 

cin.get();


 

 

 

return 0;


}
————————————
 

 

我们的测试程序中的sort(test.begin(),test.end())是STL里通用算法,从这些对比中,可见STL的算法要比这些算法好得多,那么他是如何实现的呢?啊……我真的不知道,他是不是和快速算法有关的呢?说实在的,我真不清楚,明天看看我们是否能够解开这层神秘的面纱。


 

 

今天算是为我们的类模板开个头吧。

=======================

恢复D直接查看目录

原文始发于微信公众号(

C/C++的编程教室

):第四十六讲 排序算法(1)

|

发表评论