算法分析：快速排序

快速排序（quicksort）是在實踐中最快的已知排序算法。

平均運行時間是O（NlogN），最壞的情形是O（N^2）

算法之所以特別快，主要是由于非常精煉和高度優化的內部循環。

1.如果S中元素個數是0或1，則返回

2.取S中任1元素v，成為關鍵元（pivot）

3.將S-{v}（S中其余元素）劃分成兩個不想交的集合：左側＜v，右側≥v。

4.返回左側的排序，后跟v，繼而右側的排序。

當子數組的長度小于10 的時候，使用了插入排序 算法分析：插入排序

//
//  Sort.h
//  HelloWorld
//  csdn blog：http://blog.csdn.net/u012175089
//  Created by feiyin001 on 17/1/11.
//  Copyright (c) 2017年 FableGame. All rights reserved.
//

#ifndef __HelloWorld__Sort__
#define __HelloWorld__Sort__
#include <vector>
using namespace std;
namespace Fable
{
    //選取關鍵的函數
    template<typename Comparable>
    const Comparable& median3(vector<Comparable>& a ,int left, int right)
    {
        int center = (left + right)/2;//中間的下標
        if (a[center] < a[left])
        {
            swap(a[left], a[center]);//將小的放在左側
        }
        if (a[right] < a[left])
        {
            swap(a[left], a[right]);//將小的放在左側
        }
        if (a[right] < a[center])
        {
            swap(a[center], a[right]);//將大的放在右側
        }
        swap(a[center], a[right⑴]);//將中間值放在right⑴的位置
        return a[right⑴];//返回中間值
    }
    template<typename Comparable>
    void quicksort(vector<Comparable>& a, int left, int right)
    {
        if (left + 10 <= right)//這個子數組大于10，繼續使用快速排序
        {
            Comparable pivot = median3(a, left, right);//關鍵值
            int i = left;//i指向左側
            int j = right - 1;//j指向右側，現在i和j都是已比較過的了，等下是先++和--
            while (true)
            {
                while (a[++i] < pivot) {}//小于關鍵值的元素是1直放在左側，找出1個大的元素
                while (pivot < a[--j]) {}//大于關鍵值的元素是1直放在右側，找出1個小的元素
                if (i < j)
                {
                    swap(a[i], a[j]);//i和j還沒有交匯，交換位置
                }
                else
                {
                    break;//這個時候i指向的數是應當比關鍵值大的了
                }
            }
            swap(a[i], a[right - 1]);//將關鍵值放在i的位置
            quicksort(a, left, i - 1);//分別對關鍵值左側的子數組排序
            quicksort(a, i + 1, right);//分別對關鍵值右側的子數組排序
        }
        else
        {
            //使用插入排序，數組大小小于10的時候
            insertionSort(a.begin() + left, a.begin() + right + 1);
        }
    }
    //快速排序
    template <typename Comparable>
    void quicksort(vector<Comparable>& a)
    {
        quicksort(a, 0, a.size() - 1);
    }
}

#endif /* defined(__HelloWorld__Sort__) */

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈