内部排序算法小结(原创)

文件:	内部排序算法小结.pdf
大小:	102KB
下载:	下载

内部排序算法

一、插入排序

1：直接插入排序

(1)基本思想

待排序的记录放在数组R[0…n-1]中

排序过程中某一时刻，R被划分成两个子区间R[0…i-1] (有序和)R[i…n-1](无序)

直接插入的基本操作是将当前无序区的一个记录R[i]插入到有序区R[0…i-1]中适当的位置

这种方法通常称为增量法，因为它每次使有序区增加1个记录

(2)代码

void insertsort(int R[],int n)//对R[0…n-1]按递增顺序进行直接插入排序

{

  int i,j;

  int temp;

  for(i=1;i

  {

temp=R[i];

j=i-1;//j指向有序区最后一个元素

while(j>=0&&temp

{

  R[j+1]=R[j];//将值大于R[i]的记录后移

  j--;

}

R[j+1]=temp;//在j+1处插入R[i]

  }

}

(3)性能分析

直接插入排序有两重循环：

a：对于n个记录的数组，外循环表示要进行n-1趟排序

b：每趟循环中，当R[i]>= R[i-1]时，无须进入内循环，每趟比较一次，n-1趟比较n-1次；

当R[i]，且有序区R[0…i-1]中的值均大于待插入记录R[i]值时，每趟进行i次比较；

(4)小结(直接插入排序性能)

最好时间O(n)

平均时间O(n²)

最坏时间O(n²)

稳定性--稳定

2：希尔排序

(1)基本思想

希尔排序实际上是一种分组插入的方法

先取小于n的整数d₁作为第一个增量，把数组分成d₁个组，所有距离为d₁的倍数的记录放在一个组内，在各组内进行直接插入排序；

然后，取第二个增量d₂(₁)，重复上述的分组和排序；

一直到所取的增量d_t =1，即所有记录放在同一组进行直接插入排序为止

(2)代码

void shellsort(int R[ ],int n)//对R[0…n-1]按递增顺序进行希尔排序

{

  int i,j,d;

  int temp;

  d=n/2;//d的初值取n/2

  while(d>0)

  {

for(i=d;i

{

  j=i-d;

  while(j>=0&&R[j+d]

  {

    temp=R[j];//R[j]与R[j+d]交换

    R[j]=R[j+d];

    R[j+d]=temp;

    j=j-d;

  }

}

d=d/2;//递减增量

  }

}

(3)为什么希尔排序优于直接插入排序?

当增量d=1时，希尔排序和直接插入排序基本一致！

原因：a:当n值较小时，直接插入排序的最好时间复杂度O(n)和最坏复杂度O(n²)差别不大

b:当表基本有序时，直接插入所需的比较和移动次数较少

(4)小结(希尔排序性能)

平均时间O(n^1.25)

稳定性--不稳定

二、交换排序

1：冒泡排序

(1)基本思想

整个算法是从最下面的记录开始，通过无序区相邻记录的比较和交换，使值最小的记录如气泡一般逐渐往上“漂浮”直至“水面”，经过一趟冒泡排序后，值最小的记录到达最上端；

然后，再在剩下的记录中找值次小的记录，并把它交换到第2个位置上；

依次类推，一直到所有记录都有序为止

(2)代码

void bubblesort(int R[],int n)

{

  int i,j;

  int temp;

  for(i=0;i

  {

for(j=n-1;j>i;j--)//第一趟j从1至n-1，最后一趟j取n-1

if(R[j]

{

    temp=R[j];//交换R[j]与R[j-1]，将较小值的记录前移

        R[j]=R[j-1];

        R[j-1]=temp;

}//if交换

  }//外层的for循环

}

(3)改进冒泡排序的基本思想和代码

上面的冒泡排序中，在第i(i趟时已经排好序了，但仍进行后面的几趟的比较

所以当某趟已无交换时，说明已经排好序了，算法可以结束

void bubblesort(int R[],int n)

{

  int i,j, exchange;//添加了exchange

  int temp;

  for(i=0;i

  {

    exchange=0; //添加了exchange

for(j=n-1;j>i;j--)//第一趟j从1至n-1，最后一趟j取n-1

if(R[j]

{

    temp=R[j];//交换R[j]与R[j-1]，将较小值的记录前移

        R[j]=R[j-1];

        R[j-1]=temp;

        exchange=1; //添加了exchange

}//if交换

    if(exchange=0)return; //添加了exchange

  }//外层的for循环

}

(4)性能分析(改进的冒泡排序算法)

若数组的初始状态是正序的，则一趟即可完成排序，时间复杂度为O(n)；

若数组的初始状态是反序的，则进行n-1趟排序，每次进行n-i-1次比较，时间复杂度O(n²)

(5)小结(改进的冒泡排序性能)

最好时间O(n)

平均时间O(n²)

最坏时间O(n²)

稳定性--稳定

2：快速排序

(1)基本思想            

在待排序的数组的n个元素中取一个元素(一般取第一个)，将其移动到这样的位置：在其之前的元素的值都小于它，在其之后的元素都大于它，这样是一趟快速排序；

然后对数组的两个部分进行同样的操作，直到每部分只有一个记录为止；

总之，每趟使表的第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的子表长度为1！

(2)代码

void quicksort(int R[],int low,int high)

{

  int temp;//枢轴元素

  if(low判断入参low，high是否有效

  {

temp=R[low];//以数组的第一个元素作为基准进行划分

int i=low,j=high;

while(i左右交替向中间扫描直到相遇

{

  while(i从右向左扫描，找到第一个值小于temp的R[j]

  if(i找到这样的R[j]，交换R[i]和R[j]，然后使i右移

  while(iR[i])i++;//从左向右扫描，找到第一个值大于temp的R[i]

  if(i找到这样的R[i]，交换R[i]和R[j]，然后使j左移

}

R[i]=temp;//枢轴元素移到合适的位置

    quicksort(R,low,i-1);

    quicksort(R,i+1,high);

}//结束if

}

(3)小结(快速排序性能)

最好时间O(nlogn)

平均时间O(nlogn)

最坏时间O(n²)

解释：在所有同数量级(O(nlogn))的排序方法中，快速排序被认为是平均性能最好的一种；

      但是，若初始记录序列按关键字有序或基本有序时，快速排序则蜕化为冒泡排序，此时，算法的时间复杂度为O(n²)

稳定性--不稳定

三、选择排序

1：直接选择排序

(1)基本思想(详见(3)与直接插入排序的对比)

(2)代码

void selectsort(int R[],int n)

{

  int i,j,k;

  int temp;

  for(i=0;i共n-1趟,联系以下j得第一趟从0至n-1，最后一趟n-2至n-1

  {

k=i;

for(j=i;j在当前无序区R[i…n-1]中找到最小的元素R[k]

  if(R[j]

    k=j;//用k记下目前找到的最小值的位置

if(k!=i)

{

  temp=R[i];//交换R[i]和R[k]

  R[i]=R[k];

  R[k]=temp;

}//结束if

}//结束for即n-1趟

}

(3)直接插入排序与直接选择排序的对比!

直接插入排序：把无序区第一个元素和有序区的所有元素对比，将这个无序区的第一个元素插入到有序区的适当位置，构成新的有序区如此循环

直接选择排序：找出无序区中最小的元素放在无序区的第一个位置，这样，有序区和无序区的调整后第一个位置的元素就构成了新的有序区，如此循环

(4) 小结(直接选择排序性能)

最好时间O(n²)

平均时间O(n²)

最坏时间O(n²)

稳定性--不稳定

2：堆排序

什么是堆?本文讨论的是大根堆，即概念如下：R_i>=R_2i且R_i >=R_2i+1，小根堆与之相反

(1)基本思想

首先将数组R[n]中元素按从左向右顺序排列，构成一个完全二叉树，此时，任意节点R[i]的左孩子是R[2i]，右孩子是R[2i+1]，双亲是R[i/2]；

假设完全二叉树某个节点i对它的左、右子树已经是堆，接下来要将R[2i]和R[2i+1]中的较大者与R[i]交换，但是，这有可能破坏下一级的堆，于是继续采用上述的方法构建下一级的堆，直至完全二叉树节点i构成堆为止；

对于任意一棵二叉树，从i=n/2到1，反复利用上述思想建堆，大者“上浮”，小者“下沉”!

(2)代码

调整堆的算法sift()如下：

void sift(int R[],int low,int high)//假设完全二叉树节点i对它的左、右孩子已经是堆

{

  int i=low,j=2*i;//R[j]是R[i]的左孩子

  int temp=R[i];

  while(j<=high)

  {

if(j若右孩子较大，将j指向右孩子

if(temp

{

  R[i]=R[j];//将R[j]调整到双亲节点位置上

  i=j;//修改i和j的值，以便向下筛选

  j=2*i;

}

else break;//跳出while循环

  }//while循环

  R[i]=temp;//被筛选节点的值最终放入的位置

}

堆排序的算法如下：

void heapsort(int R[],int n)//按照递增顺序排序

{

  int i;

  int temp;

  for(i=n/2;i>=0;i--)//循环建立初始堆

sift(R,i,n);

  for(i=n-1;i>=1;i--)//进行n-1趟循环，完成堆排序

  {

temp=R[0];//将当前循环内第一个元素和最后一个元素交换

R[0]=R[i];

R[i]=temp;

sift(R,0,i-1);//筛选出R[0]节点，得到i-1个节点的堆

  }//结束n-1趟循环

}

(4)小结(堆排序性能)

最好时间O(nlogn)

平均时间O(nlogn)

最坏时间O(nlogn)

稳定性--不稳定

四、其他排序算法(简略)

1：归并排序：稳定

2：基数排序：稳定

五、内部排序算法总结

1：

内部排序各种算法的性能比较(表)

	排序方法	最好时间	平均时间	最坏时间	稳定性
插入排序	直接插入排序	O(n)	O(n2)	O(n2)	稳定
	希尔排序		O(n1.25)		不稳定
交换排序	冒泡排序	O(n)	O(n2)	O(n2)	稳定
	快速排序	O(nlogn)	O(nlogn)	O(n2)	不稳定
选择排序	直接选择排序	O(n2)	O(n2)	O(n2)	不稳定
	堆排序	O(nlogn)	O(nlogn)	O(nlogn)	不稳定
其他排序	归并排序	O(nlogn)	O(nlogn)	O(nlogn)	稳定
	基数排序				稳定

 

2：内部排序各种算法的选择

(1)当n较小时：可采用直接插入排序和直接选择排序

当记录规模小时，可选择直接插入排序；

当记录规模大时，可选择直接选择排序，因为直接插入排序所需的记录移动操作比直接选择排序多

(2)当记录基本有序时：可采用直接插入排序和冒泡排序

(3)当n较大时：可采用时间复杂度为O(nlogn)的快速排序、堆排序和归并排序