快速排序算法

快速排序算法是20世纪十大最伟大的算法之一。它是由C.R.A.Hoare于1962年提出的一种划分交换排序算法，其采用的是分治的思想，分治是将原问题分解成若干与原问题相似的子问题，通过递归的解决这些子问题来最终得出原问题的解。

         快速排序是通过一个划分（SPLIT）算法来将待排序序列划分成两部分，其中左边的元素都小于中间的元素，右边的元素都小于中间的元素。然后通过对子数组进行递归划分就可以完成对整个序列的排序。所以划分（SPLIT）算法是快速排序的核心，它的伪代码如下：

算法：SPLIT

输入：数组A[low...high]

输出：1）重新排列的A；2）划分元素A[low]的新位置w；

i ← low
x ← A[low]
for j ← low+1 to high:
    if A[j] <= x then:
        i ← i+1
        if i != j then 互换A[i]和A[j]
        end if
    end if
end for
互换A[low]和A[i]
w ← i
return A和w

 

快速排序很容易用递归的方式实现，递归方式的伪代码如下：

算法：QUICKSORT

输入：n个元素的数组A[1...n]

输出：按非降序排列的数组A中的元素

quicksort(A, 1, n)

if low < high then
    SPLIT(A[low...high], w)
    quicksort(A, low, w-1)
    quicksort(A, w+1, high)
end if

 

快速排序也可以用迭代的方式实现，迭代方式伪代码如下：

算法：QUICKSORT

输入：n个元素的数组A[1...n]

输出：按非降序排列的数组A中的元素

quicksort(A, 1, n)

if low >= high then 
    return
end if

low 进栈
high 进栈
while 栈不为空:
    high = 栈顶（出栈）
    low = 栈顶（出栈）
    w = SPLIT(A, low, high)
    if low < w-1 then:
        low 进栈
        w-1 进栈
    end if
    if high > w+1 then:
        w+1 进栈
        high 进栈
    end if
end while

 

在这里只实现快速排序的迭代方式实现，C++代码实现的快排如下：

#include <iostream>
#include <stack>
#define Type int

using namespace std;

int Split(Type * a, int low, int high) {
    int i = low;
    int x = a[low];
    for (int j = low+1; j <= high; j++) {
        if (a[j] <= x) {
            i ++;
            if (i != j) {
                Type temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    Type temp = a[low];
    a[low] = a[i];
    a[i] = temp;
    
    return i;
}

void QuickSort(Type * a, int low, int high) {
    if (low >= high) {
        return;
    }
    
    stack<int> range;
    range.push(low);
    range.push(high);
    while(!range.empty()) {
        high = range.top();
        range.pop();
        low = range.top();
        range.pop();
        
        int w = Split(a, low, high);
        
        if (low < w-1) {
            range.push(low);
            range.push(w-1);
        }
        if (high > w+1) {
            range.push(w+1);
            range.push(high);
        }
    }
}

int main(void) {
    Type a[20] = {2, 3, 12, 18, 7, 8, 4, 9, 14, 12, 5, 2, 3, 17, 15, 7, 9, 11, 13 ,3};
    
    cout << "排序前：\n";
    for (int i = 0; i < 20; i ++) {
        cout << a[i] << "  ";
    } 
    cout << endl;
    
    QuickSort(a, 0, 19);
    
    cout << "迭代版快速排序后：\n";
    for (int i = 0; i < 20; i ++) {
        cout << a[i] << "  ";
    } 
    cout << endl;
    
    getchar();
    return 0;
}

 

Java版本：

package sort;

import java.util.Stack;

public class QuickSort {
	private int [] array = null;
	private boolean sorted = false;
	
	public QuickSort(int [] a) {
		this.array = new int [a.length];
		System.arraycopy(a, 0, this.array, 0, a.length);
	}
	
	private int split(int low, int high) {
		int i = low;  
	    int x = array[low];  
	    for (int j = low+1; j <= high; j++) {  
	        if (array[j] <= x) {  
	            i ++;  
	            if (i != j) {  
	                int temp = array[i];  
	                array[i] = array[j];  
	                array[j] = temp;  
	            }  
	        }  
	    }  
	    int temp = array[low];  
	    array[low] = array[i];  
	    array[i] = temp;  
	      
	    return i;
	}
	
	private void quickSort() {
		if (array.length <= 1) {
			sorted = true;
			return;
		}
		
		int low = 0, high = array.length-1;
		Stack<Integer> range = new Stack<Integer>();
		range.push(low);
		range.push(high);
		while (!range.empty()) {
			high = range.pop();
			low = range.pop();
			
			int w = split(low, high);
			
			if (low < w-1) {
				range.push(low);
				range.push(w-1);
			}
			if (high > w+1) {  
	            range.push(w+1);  
	            range.push(high);  
	        }  
		}
	}
	
	public int [] getSortedIntArray() {
		if (!sorted) {
			quickSort();
		}
		return this.array;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] a = {2, 3, 12, 18, 7, 8, 4, 9, 14, 12, 5, 2, 3, 17, 15, 7, 9, 11, 13 ,3}; 
		
		System.out.println("排序前：");
		for (int i = 0;i < 20; i ++) {
			System.out.print(a[i] + "  ");
		}
		
		QuickSort qs = new QuickSort(a);
		a = qs.getSortedIntArray();
		
		System.out.println("迭代版快速排序后：");
		for (int i = 0;i < 20; i ++) {
			System.out.print(a[i] + "  ");
		}
	}
}

 

Python版本:

#! /usr/bin/env python
# -*- coding:utf-8 -*-

def split(array, low, high):
    i = low
    x = array[low]
    for j in range(low+1, high+1):
        if array[j] <= x:
            i = i+1
            if i != j:
                temp = array[i]
                array[i] = array[j]
                array[j] = temp
    temp = array[low]
    array[low] = array[i]
    array[i] = temp

    return i

def quickSort(array, low, high):
    if low >= high:
        return

    stack_range = list()
    stack_range.append(low)
    stack_range.append(high)
    while len(stack_range) != 0:
        high = stack_range.pop()
        low = stack_range.pop()

        w = split(array, low, high)

        if low < w-1:
            stack_range.append(low)
            stack_range.append(w-1)
        if high > w+1:
            stack_range.append(w+1)
            stack_range.append(high)

if __name__ == '__main__':
    a = [2, 3, 12, 18, 7, 8, 4, 9, 14, 12, 5, 2, 3, 17, 15, 7, 9, 11, 13 ,3]

    print '排序前：'
    for i in a:
        print i,
    print

    quickSort(a, 0, len(a)-1)

    print '迭代排序后：'
    for i in a:
        print i,

鉴于本人水平有限，有错误欢迎指正。