go-数据结构[10]-快速排序

go 评论

快速排序

快速排序是图灵奖得主 C. R. A. Hoare 于 1960 年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步：

在数据集之中，选择一个元素作为”基准”（pivot）。
所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

分区是快速排序的主要内容，用伪代码可以表示如下：

1
2
3
4
5
6
7
8
9
10
function partition(a, left, right, pivotIndex)
     pivotValue := a[pivotIndex]
     swap(a[pivotIndex], a[right]) // 把 pivot 移到結尾
     storeIndex := left
     for i from left to right-1
         if a[i] < pivotValue
             swap(a[storeIndex], a[i])
             storeIndex := storeIndex + 1
     swap(a[right], a[storeIndex]) // 把 pivot 移到它最後的地方
     return storeIndex // 返回 pivot 的最终位置

首先，把基准元素移到結尾（如果直接选择最后一个元素为基准元素，那就不用移动），然后从左到右（除了最后的基准元素），循环移动小于等于基准元素的元素到数组的开头，每次移动 storeIndex 自增 1，表示下一个小于基准元素将要移动到的位置。循环结束后 storeIndex 所代表的的位置就是基准元素的所有摆放的位置。所以最后将基准元素所在位置（这里是 right）与 storeIndex 所代表的的位置的元素交换位置。要注意的是，一个元素在到达它的最后位置前，可能会被交换很多次。

一旦我们有了这个分区算法，要写快速排列本身就很容易：

1
2
3
4
5
6
procedure quicksort(a, left, right)
    if right > left
        select a pivot value a[pivotIndex]
        pivotNewIndex := partition(a, left, right, pivotIndex)
        quicksort(a, left, pivotNewIndex-1)
        quicksort(a, pivotNewIndex+1, right)

过程

举例来说，现有数组 arr = [3,7,8,5,2,1,9,5,4]，分区可以分解成以下步骤：

首先选定一个基准元素，这里我们元素 5 为基准元素（基准元素可以任意选择）：

1
2
3
          pivot
            ↓
3   7   8   5   2   1   9   5   4

将基准元素与数组中最后一个元素交换位置，如果选择最后一个元素为基准元素可以省略该步：

1
2
3
                              pivot
                                ↓
3   7   8   4   2   1   9   5   5

从左到右（除了最后的基准元素），循环移动小于基准元素 5 的所有元素到数组开头，留下大于等于基准元素的元素接在后面。在这个过程它也为基准元素找寻最后摆放的位置。循环流程如下：

循环 i == 0 时，storeIndex == 0，找到一个小于基准元素的元素 3，那么将其与 storeIndex 所在位置的元素交换位置，这里是 3 自身，交换后将 storeIndex 自增 1，storeIndex == 1：

1
2
3
4
5
                                pivot
                                  ↓
  3   7   8   4   2   1   9   5   5
  ↑
storeIndex

循环 i == 3 时，storeIndex == 1，找到一个小于基准元素的元素 4：

1
2
3
4
5
     ┌───────┐                 pivot
     ↓       ↓                   ↓
 3   7   8   4   2   1   9   5   5
     ↑       ↑
storeIndex   i

交换位置后，storeIndex 自增 1，storeIndex == 2：

1
2
3
4
5
                              pivot
                                ↓
3   4   8   7   2   1   9   5   5
        ↑           
   storeIndex

循环 i == 4 时，storeIndex == 2，找到一个小于基准元素的元素 2：

1
2
3
4
5
        ┌───────┐             pivot
        ↓       ↓               ↓
3   4   8   7   2   1   9   5   5
        ↑       ↑
   storeIndex   i

交换位置后，storeIndex 自增 1，storeIndex == 3：

1
2
3
4
5
                              pivot
                                ↓
3   4   2   7   8   1   9   5   5
            ↑           
       storeIndex

循环 i == 5 时，storeIndex == 3，找到一个小于基准元素的元素 1：

1
2
3
4
5
            ┌───────┐         pivot
            ↓       ↓           ↓
3   4   2   7   8   1   9   5   5
            ↑       ↑
       storeIndex   i

交换后位置后，storeIndex 自增 1，storeIndex == 4：

1
2
3
4
5
                              pivot
                                ↓
3   4   2   1   8   7   9   5   5
                ↑           
           storeIndex

循环 i == 7 时，storeIndex == 4，找到一个小于等于基准元素的元素 5：

1
2
3
4
5
                ┌───────────┐ pivot
                ↓           ↓   ↓
3   4   2   1   8   7   9   5   5
                ↑           ↑
           storeIndex       i

交换后位置后，storeIndex 自增 1，storeIndex == 5：

1
2
3
4
5
                              pivot
                                ↓
3   4   2   1   5   7   9   8   5
                    ↑           
               storeIndex

循环结束后交换基准元素和 storeIndex 位置的元素的位置：

1
2
3
4
5
                  pivot
                    ↓
3   4   2   1   5   5   9   8   7
                    ↑           
               storeIndex

那么 storeIndex 的值就是基准元素的最终位置，这样整个分区过程就完成了。

go语言实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package main

import "fmt"
//打印
func print(arr []int){

	for  _,data := range arr{
		fmt.Printf("%d ",data)
	}

	fmt.Println()
}


func main(){

	//arr:= []int{8, 5, 2, 6, 9, 3, 1, 4, 0, 7}
	arr:=[]int{1,3,2,4,9,2,6,5,4,8}
	print(arr)

	quicksort(arr)

	print(arr)
}

//快速排序
func quicksort(arr []int){

	//print(arr)
	length := len(arr)

	if length <2{
		return
	}
		index:= 0
		start := 0

		for i:=1;i<length;i++{

			if arr[i] <= arr[start]{
				index++
				temp:= arr[index]
				arr[index] = arr[i]
				arr[i] = temp
			}
		}

		tmp:= arr[index]
		arr[index] = arr[start]
		arr[start] = tmp

		quicksort(arr[start:index])
		quicksort(arr[index+1:length])
}

快速排序第二种方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
Copyright © 2018 jonson
*/
package main
import "fmt"
//打印
func show(arr []int){
	for i:=0;i<len(arr);i++{
		fmt.Println(arr[i])
	}
	fmt.Println("----------------------------------------------")
}

func main(){
   k := []int{1,3,2,4,9,2,6,5,4,8}
	show(k)
	quicksort(k)
	show(k)
}

func quicksort(arr []int){

	if len(arr) >1{//必须要长度大于1才有意义。

		end := len(arr)
		i := 0
		j := len(arr)

		for i<j{
			for i < end-1{
				i++
				if arr[i] <= arr[0]{
					break
				}
			}

			for j>0{
				j--
				if arr[j]>=arr[0]{
					break
				}
			}
			//如果i<j，说明要将这两个元素交换
			if i < j{
				temp :=arr[i]
				arr[i] = arr[j]
				arr[j] = temp
			}
		}

		//交换start和 j  。 到此为止， j之前为小于start元素的，j之后为大于start元素的。
		tmp := arr[j]
		arr[j] = arr[0]
		arr[0] = tmp

		//递归下去
		if j >0 {
			quicksort(arr[0:j])
		}

		if j+1 < end{
			quicksort(arr[j+1:end])
		}
	}
}

c语言实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<stdio.h>
#include<stdlib.h>
//打印
void show(int *a,int length)
{
	for (int i = 0; i < length; i++)
	{
		printf("%d\n", a[i]);
	}
	printf("---------------------------\n");
}
//快速排序,不仅要写出来，而且要优美

//arr 为数组
//start 为开始的元素的下标
//end  为结束的元素的下标+1
void quick_sort(int *arr, int start, int end)
{
	if (start < end) //必须要开始的元素 <结束的元素才有意义。
	{
		//赋值
		int i = start;
		int j = end;

		//i在++，j在--。第一个do为当i<j时就继续下去。
		do
		{
			do //此do一直让i++，直到，发现大于start的
			{
				i++;
			} while (i < end  && arr[i] < arr[start]);

			do//此do一直让j--，直到，发现小于start的元素
			{
				j--;
			} while (j>start && arr[j]>arr[start]);
			//如果i<j，说明要将这两个元素交换
			if (i < j)
			{
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		} while (i<j);
		//交换start和 j  。 到此为止， j之前为小于start元素的，j之后为大于start元素的。
		int temp = arr[j];
		arr[j] = arr[start];
		arr[start] = temp;

		//递归下去
		quick_sort(arr, start, j);
		quick_sort(arr, j + 1, end);
	}
}
void main()
{
	int a[10] = { 1,3,2,4,9,2,6,5,4,8 };
	show(a, 10);
	quick_sort(a, 0,10);
	show(a, 10);
	system("pause");
}

c语言实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<stdio.h>
#include<stdlib.h>
//打印
void show(int *a,int length)
{
	for (int i = 0; i < length; i++)
	{
		printf("%d\n", a[i]);
	}
	printf("---------------------------\n");
}
//快速排序,不仅要写出来，而且要优美

//arr 为数组
//start 为开始的元素的下标
//end  为结束的元素的下标+1
void quick_sort2(int *arr, int start, int end)
{
	if (start < end) { //start < end 才有进新下去的意义。
		//i从第一个开始，记录下标。
		int  i = start;
		//从第二个元素开始，循环到末尾
		for (int j = start+1; j < end; j++)
		{
			//一旦发现比其start小的
			if (arr[j] > arr[start])
			{
				//i++,很重要的一步，也就是让发现的小于start的数，依次放置在第2个，第3个....位置上。
				i++;
				//交换
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		////交换start和i  。 到此为止， i之前为小于start元素的，i之后为大于start元素的。
		int temp = arr[i];
		arr[i] = arr[start];
		arr[start] = temp;
		//递归
		quick_sort2(arr, start, i);
		quick_sort2(arr, i+1, end);
	}
}
void main()
{
	int a[10] = { 1,3,2,4,9,2,6,5,4,8 };
	show(a, 10);
	quick_sort2(a, 0,10);
	show(a, 10);
	system("pause");
}

JavaScript 语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function quickSort(arr) {　　
    if (arr.length <= 1) {
        return arr;
    }　　
    var pivotIndex = Math.floor(arr.length / 2);　　
    var pivot = arr.splice(pivotIndex, 1)[0];　　
    var left = [];　　
    var right = [];　　
    for (var i = 0; i < arr.length; i++) {　　　　
        if (arr[i] < pivot) {　　　　　　
            left.push(arr[i]);　　　　
        } else {　　　　　　
            right.push(arr[i]);　　　　
        }　　
    }　　
    return quickSort(left).concat([pivot], quickSort(right));
}

JavaScript 语言实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//上面简单版本的缺点是，它需要Ω(n)的额外存储空间，也就跟归并排序一样不好。额外需要的存储器空间配置，在实际上的实现，也会极度影响速度和高速缓存的性能。

function quickSort(array) {
	// 交换元素位置
	function swap(array, i, k) {
		var temp = array[i];
		array[i] = array[k];
		array[k] = temp;
	}
	// 数组分区，左小右大
	function partition(array, left, right) {
		var storeIndex = left;        
		var pivot = array[right]; // 直接选最右边的元素为基准元素
		for (var i = left; i < right; i++) {
			if (array[i] < pivot) {
				swap(array, storeIndex, i);
				storeIndex++; // 交换位置后，storeIndex 自增 1，代表下一个可能要交换的位置
			}
		}
		swap(array, right, storeIndex); // 将基准元素放置到最后的正确位置上
		return storeIndex;
	}
	function sort(array, left, right) {
		if (left > right) {
			return;
		}
		var storeIndex = partition(array, left, right);
		sort(array, left, storeIndex - 1);
		sort(array, storeIndex + 1, right);
	}
	sort(array, 0, array.length - 1);
	return array;
}

JavaScript 语言实现3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function quickSort(arr) {
    return sort(arr, 0, arr.length - 1);
    function swap(arr, i, k) {
        var temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
    function sort(arr, start, end) {
        sort(arr, 0, arr.length - 1);
        return arr;
        function swap(arr, i, k) {
            var temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
        function sort(arr, start, end) {
            if (start >= end) return;
            var pivot = arr[start],
                i = start + 1,
                k = end;
            while (true) {
                while (arr[i] < pivot) {
                    i++;
                }
                while (arr[k] > pivot) {
                    k--;
                }
                if (i >= k) {
                    break;
                }
                swap(arr, i, k);
            }
            swap(arr, start, k);
            sort(arr, start, Math.max(0, k - 1));
            sort(arr, Math.min(end, k + 1), end);
        }
    }
}

资料

郑建勋（jonson）Gopher & 区块链工程师

灾难总是接踵而至，这正是世间的常理。你以为只要哭诉一下，就会有谁来救你？如果失败了，就只能说明我不过是如此程度的男人