快速排序的递归和非递归实现 -----C++、JAVA代码实现

快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序，已达到整个序列有序.
快速排序是一种不稳定的排序方法，其平均时间复杂度为:O(NlogN)，最坏的情况是O（N*N）
特别注意：快速排序中用到的Partition函数，它的作用是进行一趟快速排序，返回“参考目标”的最终位置p,经过Partition处理之后,p左边的记录关键字均不大于参考目标,p右边的记录关键字均不小于参考目标。 Partition函数在找出数组中最大或最小的k个记录也很有用.
C++代码如下：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

template <typename Comparable>

int partition(vector<Comparable> &vec,int low, int high){
    Comparable pivot = vec[low];
    while (low<high)
    {
        while (low<high && vec[high]>=pivot)
        {
            high--;
        }
        vec[low] = vec[high];
        while (low <high&&vec[low]<=pivot)
        {
            low++;
        }
        vec[high] = vec[low];
    }
    vec[low] = pivot;
    return low;
}

//使用递归快速排序
template<typename Comparable>
void quicksort1(vector<Comparable> &vec,int low ,int high){
    if (low <high)
    {
        int mid = partition(vec, low, high);
        quicksort1(vec, low, mid - 1);
        quicksort1(vec, mid + 1, high);
    }

}

//其实就是用栈保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，对这段子序列进行partition操作,
//每次得到的mid都是vector的最终位置，知道栈中不需要放入，也没有数据时，循环结束
template<typename Comparable>
void quicksort2(vector<Comparable> &vec, int low, int high){
    stack<int> st;
    if (low<high)
    {
        int mid = partition(vec, low, high);
        if (low<mid-1)
        {
            st.push(low);
            st.push(mid - 1);
        }
        if (mid+1<high)
        {
            st.push(mid + 1);
            st.push(high);
        }

        while (!st.empty())
        {
            int q = st.top();
            st.pop();
            int p = st.top();
            st.pop();
            mid = partition(vec, p, q);
            if (p<mid-1)
            {
                st.push(p);
                st.push(mid - 1);
            }
            if (mid+1<q)
            {
                st.push(mid + 1);
                st.push(q);
            }
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int a[10] = { 12, 21, 33, 4, 50, 62, 71, 52,111,9 };
    vector<int> vec(a, a + 10);
    int len = vec.size();
    //quicksort1(vec, 0, len - 1);
    quicksort2(vec, 0, len - 1);
    for (int i=0; i < len;i++)
    {
        cout << vec[i]<< endl;
    }
    system("pause");
    return 0;
}

`
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

java代码实现：

package com.bineraytree.test;

import java.util.Stack;

public class StackTest {

    protected static int partition(int arr[],int low,int high) {
        int i=low,j=high;
        int temp=arr[low];
        while(i<j) {
            while (i<j&& temp <= arr[j])
                --j;
            arr[i] = arr[j];
            while(i<j && temp >= arr[i]) 
                ++i;
            arr[j] = arr[i];

        }
        arr[i] = temp;
        return i;
    }
    //递归排序
    public static void quickSort1(int arr[],int low,int high){
        if(low < high) {
            int mid = partition(arr, low, high);
            quickSort1(arr, low, mid-1);
            quickSort1(arr, mid+1, high);
        }
    }

    //非递归实现
    public static void quickSort2(int arr[],int low,int high) {
        Stack<Integer> st = new Stack<Integer>();
        if (low < high) {
            int mid = partition(arr, low, high);
            if (mid-1 > low) {
                st.push(mid-1);
                st.push(low);
            }
            if (mid+1 < high) {
                st.push(high);
                st.push(mid+1);
            }

            while (!st.isEmpty()) {
                int q_low = st.peek();
                st.pop();
                int p_high = st.peek();
                st.pop();
                mid = partition(arr, q_low, p_high);
                if (mid-1 > q_low) {
                    st.push(mid-1);
                    st.push(q_low);
                }
                if (mid+1 < p_high) {
                    st.push(p_high);
                    st.push(mid+1);
                }
            }

        }
    }


    public static void main(String[] args) {
        int[] arr = new int[]{10,12,5,8,96,54,36,25,1,258,366};
//      Stack<int> stack = new Stack<int>();
//      for (int i = 0; i < arr.length; i++) {
//          stack.push(arr[i]);
//      }
//      System.out.println(stack.search(96)+"-------");
//      for (int i = 0; i < arr.length; i++) {
//          System.out.println(stack.peek()+"this is peek");
//          System.out.println(stack.pop()+" is outing!!");
//          System.out.println(stack.isEmpty());
//      }
        quickSort1(arr,0, arr.length-1);
//      quickSort2(arr,0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85