快速排序是一種使用性非常強的排序算法，雖然它最壞的情況下時間復(fù)雜度O（N^2),但平均時間復(fù)雜度是O（N*logN）,并在內(nèi)存的使用、程序算法的復(fù)雜性上表現(xiàn)優(yōu)秀，尤其是對快速排序進(jìn)行隨機化的可能，快速排序是最使用的一種算法之一。

采用H5高端網(wǎng)站建設(shè)+css3國際標(biāo)準(zhǔn)網(wǎng)站建設(shè)，讓網(wǎng)站自動適應(yīng)用戶使用終端設(shè)備，PC、平板、手機等，一個網(wǎng)址適應(yīng)，一套內(nèi)容統(tǒng)一戰(zhàn)略，節(jié)約企業(yè)資源。創(chuàng)新互聯(lián)還提供網(wǎng)站后期營銷如：軟文發(fā)稿、友情鏈接、一元廣告等。一般建站公司不為企業(yè)填充資料，更談不上內(nèi)容策劃，結(jié)果導(dǎo)致網(wǎng)站界面優(yōu)秀，內(nèi)容卻十分空泛或整體不協(xié)調(diào)，內(nèi)容策劃、內(nèi)容填充請交給我們。

 算法思想：

  1.創(chuàng)建一個臨時變量，把數(shù)組中最右邊的值保存起來，最右邊就形成一個坑。

  2.然后找左邊大于臨時變量的那個值放到坑里，這樣左邊會形成新的坑。

  3.在找右邊小于臨時變量的那個值放到新的坑里，就這樣一直找。

  4.知道找完，最后把臨時變量放到最后形成的那個坑里。

  5.在把這個數(shù)組分成兩個子序列，特點：左邊的子序列中的數(shù)小于等于右邊的子序列中的數(shù)。

  6.在通過遞歸調(diào)用，來排序子序列。

  5.知道子序列排完，然后合并。（由于子序列是就地序列，所以合并不需要操作，排序已經(jīng)完成）

實現(xiàn)代碼：

Sort.h中

int SingleSort(int *a, int left, int right)
{
    assert(a);
  int tmp = a[right];//臨時變量保存值
        while (left < right)
     {
           //找左邊大于等于tmp的數(shù)
              while (left < right&&tmp >= a[left])
          {
                   left++;
             }
           if (left < right)
                {
                   a[right--] = a[left];//把值給右邊，然后--
           }
           //找右邊小于等于tmp的值
              while (left < right&&tmp <= a[right])
         {
                   right--;
            }
           if (left < right)
                {
                   a[left++] = a[right];//把值給左邊，然后++
           }
   }
   a[left] = tmp;
      return left;
}
void QuickSort(int *arr, int left, int right)
{
     if (arr == NULL)
    {
           return;
     }
   if (left < right)
        {
           //遞歸調(diào)用
              int div = SingleSort(arr, left, right);
             QuickSort(arr, left, div - 1);
              QuickSort(arr, div + 1, right);
     }
}
//打印函數(shù)
void Print(int *arr, int size)
{
     for (int i = 0; i < size; i++)
   {
           cout << arr[i] << " ";
  }
   cout << endl;
}

test.cpp中

#include
using namespace std;
#include "Sort.h"

void Test()
{
  int arr[] = { 3, 9, 7, 6, 1, 2, 4, 8, 0, 5 };
       QuickSort(arr, 0,sizeof(arr) / sizeof(arr[0])-1);
   Print(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{
   Test();
     system("pause");
    return 0;
}

 我曾經(jīng)看過看過一篇博客，快速排序?qū)π》秶鷶?shù)字排序會花費很多時間，通過我查詢資料得知，數(shù)字總量小于13，用直接插入排序表較好，超過這個數(shù)字用快速排序。然后我就把代碼改了一下.

//直接插入排序
void InsertSort(int *a, int size)
{
        int end;
    int tmp;
    for (int i = 0; i < size - 1; i++)
       {
           end = i;
            tmp = a[end + 1];
           while (end >= 0 && tmp
  上面的代碼還不夠好，如果快速排序是，你的運氣比較差，每次取出的數(shù)都是大或者最小，這樣的話他就會變成最壞一種情況，時間復(fù)雜度為O(N^2),為了避免這種情況，我想到一種辦法，三數(shù)取中法，
它是什么意思？
  三個數(shù)分別為最左邊，最右邊，中間這三個數(shù)，取得話，就取既不是大也不是最小的這個數(shù)，這樣就能避免上面那種情況。
//三數(shù)取中
int Mid(int *a, int left, int right)
{
        int mid = left - (left - right);
    if (a[left] < a[right])
  {
           if (a[left]>a[mid])
              {
                   return a[left];
             }
           else if (a[right] < a[mid])
              {
                   return a[right];
            }
           else
                {
                   return a[mid];
              }
   }
   else
        {
           if (a[right] > a[mid])
           {
                   return a[right];
            }
           else if (a[left] < a[mid])
               {
                   return a[left];
             }
           else
                {
                   return a[mid];
              }
   }
}
int SingleSort(int *a, int left, int right)
{
  assert(a);
  int tmp = Mid(a,left,right);//臨時變量保存值，三數(shù)取中
  while (left < right)
     {
           //找左邊大于等于tmp的數(shù)
              while (left < right&&tmp >= a[left])
          {
                   left++;
             }
           if (left < right)
                {
                   a[right--] = a[left];//把值給右邊，然后--
           }
           //找右邊小于等于tmp的值
              while (left < right&&tmp <= a[right])
         {
                   right--;
            }
           if (left < right)
                {
                   a[left++] = a[right];//把值給左邊，然后++
           }
   }
   a[left] = tmp;
      return left;
}
這樣就比較完善了，如果我不想用遞歸，該這么辦那？然后我就想到了借助棧來實現(xiàn)。
void QuickSort(int *arr, int left, int right)
{
   stack s;
 s.push(left);//壓棧數(shù)組的左下標(biāo)
     s.push(right);//壓棧數(shù)組的有下標(biāo)
    while (!s.empty())
  {
           int tmpRight = s.top();
             s.pop();
            int tmpLeft = s.top();
              s.pop();
            //把數(shù)組排序成左區(qū)間的數(shù)小于等于有區(qū)間的數(shù)
              int div = SingleSort(arr, tmpLeft, tmpRight);
               //壓棧左區(qū)間的左右兩個數(shù)的下標(biāo)
            if (tmpLeft < div - 1)
           {
                   s.push(tmpLeft);
                    s.push(div - 1);
            }
           //壓棧右區(qū)間的左右兩個數(shù)的下標(biāo)
             if (div + 1 < tmpRight)
         {
                   s.push(div + 1);
                    s.push(tmpRight);
           }
   }
}
 寫到這里，我有想到了另一種實現(xiàn)SingleSort()函數(shù)的方法，感覺比上面的更簡單，不過理解起來比較抽象。
  思想：
   1.定義一個cur為a[0]位置的下標(biāo)
   2.在定義一個prev為a[0]的前一個位置。
   3.當(dāng)a[0]位置的值小于最右邊的值。
   4.++prev,然后交換prev和cur對應(yīng)的值。
   5.如果小于最右邊的值，++prev,prev和最右邊值交換。
   6.一直進(jìn)行下去，就會讓左邊的值小于等于右邊的值。
int SingleSort(int *arr, int left, int right)
{
       int cur = left;
     int prev = cur - 1;
 int key = Mid(arr, left, right);
    swap(arr[right], key);//把key的值放到最右邊
 while (cur < right)
      {
           //++prev != cur防止自己和自己交換
            if (arr[cur]<=arr[right]&&++prev != cur)
         {
                   swap(arr[prev], arr[cur]);
          }
           cur++;
      }
   swap(arr[++prev], arr[right]);
      return prev;
}
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
            

            分享標(biāo)題：快速排序的分析與實現(xiàn)-創(chuàng)新互聯(lián)            

            網(wǎng)站URL：http://weahome.cn/article/epgdh.html