首页 > 代码库 > 快速排序总结

快速排序总结

数据结构之排序算法——快速排序

 

代码很多地方借鉴了  http://my.csdn.net/MoreWindows 他的思想,

本人认为该作者已经写的很好了,只是在他的基础上加入了一些自己的理解和说明

如果涉及到版权的问题,请联系我的邮箱,我会尽快删除

 希尔排序想关链接:

维基百科:https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F#C.E8.AA.9E.E8.A8.80

百度百科:http://baike.baidu.com/view/19016.htm

参考博客 :http://blog.csdn.net/morewindows/article/details/6684558

 

快速排序 对大量的数据具有很好的性能,

快速排序的基本思想就是,先对数组进行从右向左的扫描,找到第一不大于当前定义的关键值数,与它进行交换,然后在从左向右进行扫描,找到第一个不小于当前关键值的数,将它们交换,然后将数据分成两个部分,前面一部分都小于关键字,后面一部分都大于关键字,然后再前后的部分继续进行前面描述的操作,这就需要递归的调用自己。

 

源码如下:

void Quick_Sort(int array[], int arrayLen)

{

    Sort(array, 0, arrayLen-1);

}

 

 

void Sort(int array[],  int low, int height)

{

    if (low < height)

    {

        int retPivotkey = partition(array, low, height);

        Sort(array, low, retPivotkey - 1);

        Sort(array, retPivotkey + 1, height);

    }

}

 

 

int partition(int array[], int right, int left)

{

    // 将所有的比关键字小的元素,移动到关键字的左边,比关键字大的元素移动到关键字的右边

    int pivotkey = array[right];

    while (right < left)

    {

        while (right < left && array[left] >= pivotkey)

            -- left;

        if (right < left)

        {

            array[right++] = array[left];

        }

 

        while (right < left && array[right] < pivotkey)

            ++ right;

        if (right < left)

        {

            array[left--]=array[right] ;

        }

    }

    // 将关键字插入想关的位置

    array[right] = pivotkey;

    // 返回关键字的位置,便于下次循环

    return right;

}

源码这样写是为了和前面排序算法相互统一,我也看到了一个合并的写法

 

void Quick_Sort(int array[], int low, int height)

{

    // 将low 和 height  缓存 为后面的递归的实现提供界限

    int right = low, left = height;

 

    if (low < height)

    {  

        int pivotkey = array[right];

        while (right < left)

        {

            while (right < left && array[left] >= pivotkey)

                --left;

            if (right < left)

            {

                array[right++] = array[left];

            }

 

            while (right < left && array[right] < pivotkey)

                ++right;

            if (right < left)

            {

                array[left--] = array[right];

            }

        }

        // 将关键字插入想关的位置

        array[right] = pivotkey;

 

        Quick_Sort(array, low, right - 1);

        Quick_Sort(array, right + 1, height);

    }

}

 

在查资料的时候也看到了一个迭代的版本,这个版本来自维基百科

 维基百科链接: https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F#C.E8.AA.9E.E8.A8.80

源码如下:

typedef struct _Range {

    int start, end;

} Range;

 

Range new_Range(int s, int e) {

    Range r;

    r.start = s;

    r.end = e;

    return r;

}

 

void swap(int *x, int *y) {

    int t = *x;

    *x = *y;

    *y = t;

}

 

void quick_sort2(int arr[], const int len) {

    if (len <= 0)

        return; // 避免len为负值时出错

    // r[]模拟栈 ,p为栈中元素的数量, r[p++] 为push, r[--p] 为pop且 取得元素

    Range *r= (Range *)malloc(sizeof(Range)*len);// 因为vs 不支持c99 所以,只能动态开辟了,支持c99的可以使用 Range r[len];

    if (r == NULL)

        return;

    int p = 0;

    // 模拟栈的入栈

    r[p++] = new_Range(0, len - 1);

    while (p)

    {

        // 模拟栈的出栈

        Range range = r[--p];

 

        // 当start大于end时,结束当前循环

        if (range.start >= range.end)

            continue;

 

        int mid = arr[range.end];

 

        int left = range.start, right = range.end - 1;

 

        while (left < right)

        {

            // 找到第一个不小于mid的元素

            while (arr[left] < mid && left < right)

                left++;

            // 找到第一个不大于mid的元素

            while (arr[right] >= mid && left < right)

                right--;

 

            swap(&arr[left], &arr[right]);

        }

 

        // 避免数组元素越界

        if (arr[left] >= arr[range.end])

        {

            swap(&arr[left], &arr[range.end]);

        }

 

        else

        {

            // 如果left 指针没有越界

            left++;

        }

        // 将左右两个部分的范围入栈

        r[p++] = new_Range(range.start, left - 1);

        r[p++] = new_Range(left + 1, range.end);

    }

 

    free(r);

}

快速排序总结