go语言实现快速排序

先看一下c++的实现方法：

1、快速排序的描述

　　快速排序算法采用的分治算法，因此对一个子数组A[p…r]进行快速排序的三个步骤为：

（1）分解：数组A[p...r]被划分为两个（可能为空）子数组A[p...q-1]和A[q+1...r]，给定一个枢轴，使得A[p...q-1]中的每个元素小于等于A[q]，A[q+1...r]中的每个元素大于等于A[q]，q下标是在划分过程中计算得出的。

　　（2）解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1...r]进行排序。

　　（3）合并：因为两个子数组是就地排序，不需要合并操作，整个数组A[p…r]排序完成。

　　快速排序关键过程是对数组进行划分，划分过程需要选择一个主元素（pivot element）作为参照，围绕着这个主元素进划分子数组。举个列说明如何划分数组，现有子数组A={24，15，27，5，43，87，34}，以最后一个元素为主元素进行划分，划分过程如图所示：

PARTITION(A,p,r)  
//将最后一个元素作为主元素  
  i = p-1  
for j=p to r-1     //从第一个元素开始到倒数第二个元素结束，比较确定主元的位置  
do if A[j] <= x  
             i = i+1  
             exchange A[i] <-> A[j]  
//最终确定主元的位置  
return i+1   //返回主元的位置

根据划分过程的为代码，书中又给出了快速排序的为代码：

1 QUICKSORT(A,p,r)
2     if p<r
3        q = PARTITION(A,p,r)    //确定划分位置
4        QUICKSORT(A,p,q-1)     //子数组A[p...q-1]
5        QUICKSORT(Q,q+1,r)     //子数组A[q+1...r]

好了理解了就可以根据伪代码来写测试：

#include<iostream>  

using namespace std;  

void swap(int *x, int *y)  
{  
int tmp = *x;  
    *x = *y;  
    *y = tmp;  
}  

//划分数组  
int partition(int a[], int begin, int last)  
{  
int x = a[last];  
int i = begin - 1;  
for (int j = begin; j < last; j++)  
    {  
if (x <= a[j])  
        {  
            i=i+1;  
            swap(&a[i], &a[j]);  
        }  
    }  
    swap(&a[i+1], &a[last]);  

return (i + 1);  
}  

//利用递归排序  
void quick_sort(int a[], int begin, int last)  
{  
if (begin < last)  
    {  
int q = partition(a, begin, last);  
        quick_sort(a, begin, q-1);  
        quick_sort(a, q + 1, last);  
    }  
}  

int main()  
{  
int i;  
int a[] = { 88, 1, 22, 99, 55, 77, 33, 66, 44, 70 };  
"After the quick sort,the data is:" << endl;  
    quick_sort(a, 0, 9);  

for (const auto i : a)  
" ";  
    cout << endl;  

return 0;  
}

go语言实现快速排序

2.go语言的方法

先说明这个快速排序法的概念，它以最右边的值s作比较的标准，将整个数列分为三个部份，一个是小于s的部份，一个是大于s的部份，一个是未处理的部份，如下所示：

go语言实现快速排序

在排序的过程中，i 与 j 都会不断的往右进行比较与交换，最后数列会变为以下的状态：

go语言实现快速排序

然后将s的值置于中间，接下来就以相同的步骤会左右两边的数列进行排序的动作，如下所示：

go语言实现快速排序

整个演算的过程，直接摘录书中的虚拟码来作说明：

QUICKSORT(A, p, r)     if p < r 
        then q <- PARTITION(A, p, r) 
                 QUICKSORT(A, p, q-1) 
                 QUICKSORT(A, q+1, r) 
end QUICKSORT 

PARTITION(A, p, r) 
    x <- A[r] 
    i <- p-1 
    for j <- p to r-1 
        do if A[j] <= x 
                 then  i <- i+1 
                         exchange A[i]<->A[j] 
    exchange A[i+1]<->A[r] 
    return i+1 
end PARTITION

一个实际例子的演算如下所示：

go语言实现快速排序

具体代码如下：

package main

import (
  "fmt"
)

const MAX = 10

var sortArray = []int{41, 24, 76, 11, 45, 64, 21, 69, 19, 36}

func main() {

  fmt.Println("before sort：")
  show()

  quickSort(sortArray, 0, MAX-1)

  fmt.Println("after sort:")
  show()

}

func quickSort(sortArray []int, left, right int) {
  if left < right {
    pos := partition(sortArray, left, right)
    partition(sortArray, left, pos-1)
    partition(sortArray, pos+1, right)
  }
}

func partition(sortArray []int, left, right int) int {
  key := sortArray[right]
  i := left - 1

  for j := left; j < right; j++ {
    if sortArray[j] <= key {
      i++
      swap(i, j)
    }
  }

  swap(i+1, right)

  return i + 1
}

// Swap the position of a and b
func swap(a, b int) {
  sortArray[a], sortArray[b] = sortArray[b], sortArray[a]
}

// foreach
func show() {
  for _, value := range sortArray {
    fmt.Printf("%d\t", value)
  }
}

秒客网

go语言实现快速排序

相关文章