扰人心智之“快排序”

100 阅读 0 评论 66 点赞

我是靠谱客的博主痴情黄蜂，最近开发中收集的这篇文章主要介绍扰人心智之“快排序”，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在众多排序的学习过程中，快排序的写法是我花费时间较长的。第一次接触这个“厉害人物”，看到了他帅气的外表，却看不透他复杂的内心，因此激发了我的好奇心。而要用我喜爱的MATLAB来征服他确实废了好大功夫，不开心的是过程好艰难，开心的是 I got it . OK，记录我的小日志吧。。。。。。。。。。。。

快排序（Quick Sort）主体思想：

Step 1: 分区：取定一个分区点 pivot ，遍历一次数组，将所有比 pivot 小的数都放在 pivot 的前面，把所有比 pivot 大的数都放在pivot 的后面，比如下面一个数组

6 11 3 9 8（pivot ）

取定 8 为 pivot 经过一次排序得到

6 3 8（pivot ） 9 11 分区

Step 2: 递归：将 pivot 前面和后面的两组数按照上面方法分区，如此迭代，直至最后得到一个有小到大排序的新数组。

分区一次的单独代码（MATLAB）：

---------------------------------------------------------------------------------------------

%快排序算法原地排序一次  Quick Sort （once），输出分区后的数组和分区点pivot的位置
% 输入一个数组，将最后一个数据作为分区点pivot，将整组数据分为三块：pivot左边（比pivot小）；pivot ；pivot右边（比pivot大）

function [array,i]=QuickSort_once(array)  
% 定义函数Quick_Sort_once，参数array是一个数组

n=length(array);     % 计算数组的长度
pivot=array(n);
i=1;

for j=1:1:(n-1)
    if array(j)<pivot
        tmp=array(j);
        array(j)=array(i);
        array(i)=tmp;
        i=i+1;
    end
end

value=array(n);
array(n)=array(i);
array(i)=value;
end

快排序（MATLAB）：

---------------------------------------------------------------------------------------------

% 快排序法 Quick Sort
% 输入一个数组，经过运算，使数组从小到大排列

function array = QuickSort(array,low,high)  
% 测试 array=QuickSort([2 12 6 4 7 10 8],1,7)

if low < high
    [array,i] = Partition(array,low,high);
    if low < i
        array = QuickSort(array,low,i-1);  %pivot前面数组递归分区
    end
    if i < high
        array = QuickSort(array,i+1,high);   %pivot后面数组递归分区
    end
end
end

% ----------分区
function [array,i] = Partition(array,low,high) 
% 定义函数Quick_Sort，参数array是一个数组

pivot = array(high);
i = low;
if low < high
    for j = low:1:(high-1)
        if array(j) < pivot
            tmp = array(j);
            array(j) = array(i);
            array(i) = tmp;
            i = i+1;
        end
    end
%交换
value = array(high);
array(high) = array(i);
array(i) = value;
end
end

% 测试一

>> array=QuickSort([2 12 6 4 7 10 8],1,7)

array =

     2     4     6     7     8    10    12

% 测试二

>> array=QuickSort([20 5 13 3 54 1 12 6 4 7 10 24 9 13 8],1,15)

array =

  Columns 1 through 13

     1     3     4     5     6     7     8     9    10    12    13    13    20

  Columns 14 through 15

    24    54

---------------------------------------------------------------------------------

遗憾的是，我真的好困好困，没能完成我的试验部分数据，而且又发现了代码的小失误。但真的想完成每天的小记录，就等我好好地睡饱，明日好好完善！嗯，姑娘还是要有美容觉的。。。。