劍指offer之快速排序

1 快速排序

通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列

2 分析思路

很明顯，先是用到了 partition算法思想（前面的部落格提到了），然後再把原始資料分成幾部分然後遞歸同樣用partition算法處理

3 代碼實作

1) 代碼實作方式1

#include <iostream>
#include <vector>
 
using namespace std;
 
/*
 *交換函數
 */
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
/*
 * 列印vector
 */
void printVector(vector<int> v) 
{
    for (int i = 0; i < v.size(); ++i)
    {
        std::cout << v[i] << "\t";
    }
    std::cout << std::endl;
}
 
/*
 *partition算法 記得如果這裡是C++我們傳遞的是vector類型，我們記得要加引用，
 *不然改變不了資料，這裡和java傳遞ArrayList不一樣，ArrayList作為參數可以改變集合裡面的值，
 *是以C++如果函數傳遞非基本資料類型，一半都是帶引用的
 */
int partitionOne(vector<int>& vector, int start, int end)
{
    if (start > end)
    {
        std::cout << "vector is empty or start > end" << std::endl;
        return -1;
    }
    int pivot = vector[start];
    while (start < end)
    {
        //我們先從尾巴開始
        while (start < end && pivot <= vector[end])
        {
            --end;
        }
        //這裡用的數組指派，而不是直接用swap交換函數，那麼下面的2步也是用數組指派，而不是用swap交換函數
        vector[start] = vector[end];
        while (start < end && pivot >= vector[start])
        {
            ++start;
        }
        vector[end] = vector[start];
        
    }
    vector[start] = pivot;
    printVector(vector);
    return start;
}
 
 
/*
 *partition算法, 這裡隻不過增加了2個變量i和j
 *，
 */
int partitionTwo(vector<int>& vector, int start, int end)
{
    if (start > end)
    {
        return -1;
    }
    int i = start;
    int j = end;
    int pivot = vector[start];
    while (i < j)
    {
        //我們先從尾巴開始
        while (i < j && pivot <= vector[j])
        {
            --j;
        }
        //這裡用的數組指派，而不是直接用swap交換函數，那麼下面的2步也是用數組指派，而不是用swap交換函數
        vector[i] = vector[j];
        while (i < j && pivot >= vector[i])
        {
            ++i;
        }
        vector[j] = vector[i];
    }
    vector[i] = pivot;
    printVector(vector);
    // quickSort1(vector, start, i - 1);/*最後用同樣的方式對分出來的左邊的小組進行同上的做法*/
    // quickSort1(vector, i + 1, end);
    return i;
}
 
/*
 *partition算法, 這裡隻不過增加了2個變量i和j,然後使用了交換函數swap
 *，
 */
int partitionThree(vector<int>& vector, int start, int end)
{
    if (start > end)
    {
        return -1;
    }
    int i = start;
    int j = end;
    int pivot = vector[start];
    while (i < j)
    {
        //我們先從尾巴開始
        while (i < j && pivot <= vector[j])
        {
            --j;
        }
        while (i < j && pivot >= vector[i])
        {
            ++i;
        }
        //這裡用的shiswap交換函數，那麼下面的是是也是swap交換函數
        swap(vector[i], vector[j]);
    }
    swap(vector[i], vector[start]);
    printVector(vector);
    return i;
}
 
/**
 *快速排序 調用第一個partitionOne
 */
void quickSortOne(vector<int>& vector, int start, int end)
{
    if (vector.size() < 0 || start > end)
        return;
    int index = partitionOne(vector, start, end);
    quickSortOne(vector, start, index - 1);
    quickSortOne(vector, index + 1, end);
}
 
/**
 *快速排序 調用第二個partitionTwo 
 */
void quickSortTwo(vector<int>& vector, int start, int end)
{
    if (vector.size() < 0 || start > end)
        return;
    int index = partitionTwo(vector, start, end);
    quickSortTwo(vector, start, index - 1);
    quickSortTwo(vector, index + 1, end);
}
 
 
/**
 *快速排序 調用第三個partitionThree
 */
void quickSortThree(vector<int>& vector, int start, int end)
{
    if (vector.size() < 0 || start > end)
        return;
    int index = partitionThree(vector, start, end);
    quickSortThree(vector, start, index - 1);
    quickSortThree(vector, index + 1, end);
}
 
int main()
{
    vector<int> v1;
    //[5,9,2,1,4,7,5,8,3,6]
    v1.push_back(5);
    v1.push_back(9);
    v1.push_back(2);
    v1.push_back(1);
    v1.push_back(4);
    v1.push_back(7);
    v1.push_back(5);
    v1.push_back(8);
    v1.push_back(3);
    v1.push_back(6);
 
    std::cout << "old data print " << std::endl;
    printVector(v1);
 
    quickSortOne(v1, 0, v1.size() - 1);
    // quickSortTwo(v1, 0, v1.size() - 1);
    // quickSortThree(v1, 0, v1.size() - 1);
 
    std::cout << "after partitionOne" << std::endl;
    printVector(v1);
 
    return 0;
}      

運作結果如下

old data print 
5   9   2   1   4   7   5   8   3   6   
3   4   2   1   5   7   5   8   9   6   
1   2   3   4   5   7   5   8   9   6   
1   2   3   4   5   7   5   8   9   6   
1   2   3   4   5   7   5   8   9   6   
1   2   3   4   5   7   5   8   9   6   
1   2   3   4   5   6   5   7   9   8   
1   2   3   4   5   5   6   7   9   8   
1   2   3   4   5   5   6   7   9   8   
1   2   3   4   5   5   6   7   8   9   
1   2   3   4   5   5   6   7   8   9   
after partitionOne
1   2   3   4   5   5   6   7   8   9   
 
       

上面我們寫了3個parition函數，我們調用quickSortOne(v1, 0, v1.size() - 1)或者quickSortTwo(v1, 0, v1.size() - 1)或者quickSortThree(v1, 0, v1.size() - 1)其中的的一個，結果都是一樣。