十分钟搞定一个算法-快速排序

算法在面试笔试中是十分重要的，话不多说，认真观看，十分钟后，你会掌握快速排序。

在各个公司的面试中，快排是一个高频点，不止要求你讲清原理会写代码，甚至要求你手写代码。

快速排序利用了分治法，什么是分治？简单来说 分治就是把一个问题分割成若干个小问题，分别解决。

快速排序的基本思想就是：

1、从数组中选择一个基准数（可以用第一个元素作为基准数）

2、进行分区，使基准数左边的元素都小于等于它，基准数右边的都大于它。这样就分成了两个区。

注：第一步和第二步可以抽象成一个quick_sort函数，这个函数的主要作用就是完成分区。

3、对左右分区都重复进行第一，二步，直到每个分区都只有一个元素为止。

这第三个步骤转化成编程的思想就相当于递归调用quick_sort函数。

演示：

对6，5，7，4，3，8，9这七个数进行快速排序排序。大概的步骤如下：

1、选择第一个元素arr[0]=6为基准数，

2、进行分区，分区结果是：

   3，5，4，6，7，8，9

步骤2的分区逻辑如下：

i=0;
j=arr.length-1;
X=arr[i];    //X是选定的基准元素
while(i < j)
{

while(i < j && s[j] > x){// 从右向左找第一个小于x的数

j--;

}
if(i < j){

s[i++] = s[j];

}
while(i < j && s[i] <= x){// 从左向右找第一个大于等于x的数

i++;

}
if(i < j){

s[j--] = s[i];

}
s[i] = x;
}

每一个循环完成的排序结果如下：

3,5,7,4,[6],8,9

3,5,[6],4,7,8,9

3,5,4,[6],7,8,9

3、对第二步得到的两个分区分别重复进行选基准数并进行分区，重新选择基准数和分区相当于递归调用。

左边分区元素有3，5，4，右边分区元素有7，8，9

左边分区3，5，4逻辑如下：

1、选择分区的第一个元素3为基准数

2、分区结果是3，5，4。 3是基准元素，3左面无元素视为皆比基准数3小，3右面元素皆比基准数3大，故分区结果为3，5，4

3、步骤二分区后，左分区0个元素，右分区有两个元素5，4，因为右分区有两个元素，所以还要进行排序

5，4进行分区排序，排序后的元素为4，5

所以左分区3，5，4进行分区排序后得到元素3，4，5

右边分区7，8，9逻辑和左边分区一样。分区结果是7，8，9

整体代码如下：

void quick_sort(int s[],int l,int r)

{

if(l < r)

{

//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换

int i = l, j = r, x = s[l];

while(i < j)

{

while(i < j && s[j] >= x)// 从右向左找第一个小于x的数

j--;

if(i < j)

s[i++] = s[j];

while(i < j && s[i] < x)// 从左向右找第一个大于等于x的数

i++;

if(i < j)

s[j--] = s[i];

}

s[i] = x;

quick_sort(s, l, i - 1);// 递归调用

quick_sort(s, i + 1, r);

}

}

main函数中调用：quick_sort（array，0，array.length）

关注公众号：coderTO，有问题直接公众号留言即可