快速排序的实现 引

发表于

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

引

说到快速排序，可能大家都不会陌生。今天的算法课程中，学到了快速排序的两种中间实现步骤，给大家分享一下。

1.快速排序的思想

首先还是过一遍快速排序的基本思想。

用我自己的话总结一下，就是：

  1. 在比较序列中取关键值key
  2. 将序列中比key值大的放在key的一侧，比key值小的放在另一则
  3. 分别对左右两侧重复进行1、2操作

从步骤中我们能够清晰地明白这是一种分而治之的思想，因此在代码中的体现就是使用递归。

2.对于步骤2的解析

作为算法的主要部分，我们需要知道如何实现步骤2，即将大的放在一边，小的放在另一边。

从字面上来看，这个步骤似乎实现起来并不难，但我们的算法依然有许多考究之处。

v2-d4e5d0a778dba725091d8317e6bac939_b.gif

[图片来源](【算法】排序算法之快速排序 - 知乎 (zhihu.com))

2.1

左右分开找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
js复制代码int partition(int arr[], int low, int high){
    int key;
    key = arr[low];
    while(low<high){
        while(low <high && arr[high]>= key )
            high--;
        if(low<high)
            arr[low++] = arr[high];
        while( low<high && arr[low]<=key )
            low++;
        if(low<high)
            arr[high--] = arr[low];
    }
    arr[low] = key;
    return low;
}

具体思路参考下图

20190320151833851.gif
图片来源

2.2

从一端“过滤”

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
js复制代码

int partition(int arr[], int low, int high){
    int i=high;
    int m=high;
    int key =arr[high];
    
    while(i>=low){
    	if(arr[i]>key){
    		int temp=arr[m];
    		arr[i]=arr[m];
    		arr[m]=temp;
    		m--;
		}
	    i--;
	}
	int temp=arr[high];
	arr[high]=arr[m+1];
	arr[m+1]=temp;
	printf("\n%d",m);
    return m+1;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%