快速排序(C语言实现)

1.起因
今天在acm刷题的时候,之前的排序算法一直都是冒泡,可能九度OJ的难度题考察的都是快速排序,导致我都是死在time limited上,因此我下决心要学习一下快速排序,心得跟大家进行分享!

2.算法思想
快速排序采用了一种分治策略,我感觉它就是归并排序的优化,学术上称之为分治法(Divide-and-ConquerMethod)
(1)分治的基本思想:
将原问题分解成若干个规模更小但是结构跟原问题相似的子问题。递归的解决这些子问题,然后将这些子问题的解喝并为原问题的解
(2)快速排序的思想:
设当前需要排序的数组为int A[low..high]
分解:
在A[]中任选一个记录作为基准(pivot),以pivot为基准将数组A划分为两个小的数组A[low..pivot-1]和A[pivot+1..high],并使左边的数组元素均小于等于pivot,右边数组元素均大于等于piovt。此时,pivot处于正确的位置上,它不需要再参加后续的排序
求解:
递归的调用快速排序,对A[low..pivot-1]和A[pivot+1..high]进行快速排序
组合:
跟归并排序不同,因为每次调用快速排序,左右两个数组均已有序,因此对于快速排序来说,组合是一个空操作

3.快速排序程序实现
主流程:

/**
 * Description:快速排序主流程
 */ 
void quicksort(int *A, int p, int r) 

    int pivot; 
 
    if( p < r) 
    { 
        pivot = partition(A, p, r); 
        quicksort(A, p, pivot - 1); 
        quicksort(A, pivot+1, r); 
    } 

注意:为排序整个数组,只需要在main函数中调用一个quicksort(A,begin,end)即可完成对数组的排序。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/95533566b1921ae7ea38c16de26fffa8.html