汉扬编程 编程大纲 经常用到的的排序(快速排序和归并排序)简单的计算机算法学习

经常用到的的排序(快速排序和归并排序)简单的计算机算法学习

1.快速排序快速排序(Quicksort)是对冒泡排序的一种改进。

经常用到的的排序(快速排序和归并排序)简单的计算机算法学习

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

经常用到的的排序(快速排序和归并排序)简单的计算机算法学习

要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它左边,所有比它大的数都放到它右边,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是:

1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;

2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];

3)从j开始向前搜索,即由后开始向前搜索(j–),找到第一个小于key的值A[j],将A[j]和A[i]的值交换;

4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]的值交换。

5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

C语言自带的快速排序:函数名称:qsort,在头文件:<stdlib.h>中

2.归并排序归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并 。

归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。

归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)

治的过程中用到了两个有序列的合并,如下图

代码如下

#include <stdlib.h>

#include <stdio.h>

void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)

{

int i = startIndex, j=midIndex+1, k = startIndex;

while(i!=midIndex+1 && j!=endIndex+1)

{

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

tempArr[k++] = sourceArr[j++];

else

tempArr[k++] = sourceArr[i++];

}

while(i != midIndex+1)

tempArr[k++] = sourceArr[i++];

while(j != endIndex+1)

tempArr[k++] = sourceArr[j++];

for(i=startIndex; i<=endIndex; i++)

sourceArr[i] = tempArr[i];

}

//内部使用递归

void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)

{

int midIndex;

if(startIndex < endIndex)

{

midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int

MergeSort(sourceArr, tempArr, startIndex, midIndex);

MergeSort(sourceArr, tempArr, midIndex+1, endIndex);

Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);

}

}

int main(int argc, char * argv[])

{

int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};

int i, b[8];

MergeSort(a, b, 0, 7);

for(i=0; i<8; i++)

printf(\”%d \”, a[i]);

printf(\”\\n\”);

return 0;

}

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/6333.html

C语言库函数之qsort()详解

C语言编程八大排序之快速排序

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部