【數(shù)據(jù)結(jié)構(gòu)】常見(jiàn)的7種比較排序算法2

● 快速排序（Quick Sort）

1、算法描述：

   在平均狀況下，排序n個(gè)數(shù)據(jù)要O(nlg(n))次比較。在最壞狀況下則需要O(n^2)次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他O(nlg(n))算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)，且在大部分真實(shí)世界的數(shù)據(jù)，可以決定設(shè)計(jì)的選擇，減少所需時(shí)間的二次方項(xiàng)的可能性。

2、步驟：

1）從數(shù)列中挑出一個(gè)元素，稱(chēng)為 “基準(zhǔn)”。

2）重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱(chēng)為分區(qū)操作。

3）遞歸把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

算法優(yōu)化：

1）如果進(jìn)行排序的區(qū)間較小，快速排序效率較低，可通過(guò)插入排序?qū)崿F(xiàn)

2）對(duì)于基準(zhǔn)的選取，利用三數(shù)取中法，就不會(huì)恰好取到最大或最小的數(shù)，避免了最快情況的發(fā)生

三數(shù)取中法（首位、中間和末尾的數(shù)據(jù)）

int GetMidOfThree(int *arr, int left, int mid, int right)//三數(shù)取中法（left，mid和right所在數(shù)據(jù)中取中間數(shù)作為“基準(zhǔn)”）
{
 assert(arr);
 if (arr[left] < arr[mid])
 {
  if (arr[mid] < arr[right])
  {
   return arr[mid];
  }
  else //arr[right]<=arr[mid]
  {
   if (arr[left] > arr[right])
    return arr[left];
   else
    return arr[right];
  }
 }
 else//arr[left]>=arr[mid]
 {
  if (arr[mid] > arr[right])
  {
   return arr[mid];
  }
  else//arr[right]>=arr[mid]
  {
   if (arr[right] > arr[left])
    return arr[left];
   else
    return arr[right];
  }
 }
}

對(duì)于步驟2，有三種實(shí)現(xiàn)方式

int PartSort1(int *arr, int left, int right)//方法一
{//使右邊均為大于key的數(shù)，左邊均為小于key的數(shù)
 assert(arr);
 int key = GetMidOfThree(arr, left, left - (left - right) / 2, right);//選取“基準(zhǔn)”下標(biāo)
 //int key = arr[left];//也可為right
 int begin = left;
 int end = right;
 while (begin < end)
 {
  while (begin < end && arr[begin] <= key)//從左往右找大于key的數(shù)
  {
   begin++;
  }
  while (begin < end && arr[end] >= key)//從右往左找小于key的數(shù)
  {
   end--;
  }
  if (begin < end)//如果begin<end進(jìn)行交換,相等也可以交換，故該if條件可以不寫(xiě)
  {
   swap(arr[begin], arr[end]);
  }
 }
 //此時(shí)begin和end相等
 if (arr[begin] > arr[right])//處理只有兩個(gè)數(shù)時(shí)eg:2 1;
 {
  swap(arr[begin], arr[right]);
 }
 return end;
}
int PartSort2(int *arr, int left, int right)//方法二：挖坑法
{
 assert(arr);
 //基準(zhǔn)為left數(shù)據(jù)，在進(jìn)行循環(huán)時(shí)先進(jìn)行右邊查找，再進(jìn)行左邊查找；基準(zhǔn)為right時(shí)，順序相反
 //這樣才能將比key大的數(shù)存放在前一部分，比key小的存放在后一部分
 //不能用三數(shù)取中法選取基準(zhǔn)【僅是個(gè)人觀點(diǎn)，如有誤請(qǐng)多多指教】
 int key = arr[left];
 int begin = left;
 int end = right;//此處從right處開(kāi)始
 while (begin < end)
 {
  while (begin < end && arr[end] >= key)//右邊找比key小的數(shù)據(jù)
  {
   end--;
  }
  if (begin < end)
  {
   arr[begin++] = arr[end];
  }
  while (begin < end && arr[begin] <= key)//左邊找比key大的數(shù)據(jù)
  {
   begin++;
  }
  if (begin < end)//埋坑。（end--）挖新坑
  {
   arr[end--] = arr[begin];
  }
 }
 arr[begin] = key;
 return end;
}
int PartSort3(int *arr, int left, int right)//方法三：此法更好些(代碼簡(jiǎn)單)，通過(guò)prev和cur遍歷一次進(jìn)行排序
{
 int key = arr[right];//不能用三數(shù)取中進(jìn)行，如果key為arr[left],則循環(huán)從后往前進(jìn)行，找大于key的數(shù)進(jìn)行交換
 int prev = left - 1;
 int cur = left;
 while (cur < right)//從左往右遇大于或等于key的數(shù)，跳過(guò)去；遇到小于key的數(shù)停下來(lái)進(jìn)行交換
 {//prev的兩種情況：1、緊跟在cur后面；2、指向比key大的前一個(gè)數(shù)
  if (arr[cur] < key && ++prev != cur)//如果prev和cur緊跟就不進(jìn)行交換
  {
   swap(arr[cur], arr[prev]);
  }
  cur++;
 }
 swap(arr[++prev], arr[right]);//將prev的后一位與最后元素進(jìn)行交換
 return prev;
}

遞歸函數(shù)的實(shí)現(xiàn)

void QuickSort(int *arr, int left, int right)
{
 assert(arr);
 if (left >= right)//遞歸退出條件
 {
  return;
 }
 if (right - left < 13)//當(dāng)區(qū)間比較小時(shí)，用插入排序（提高性能）
 {
  InsertSort(arr, right - left);
 }
 //int div = PartSort1(arr, left, right);
 //int div = PartSort2(arr, left, right);
 int div = PartSort3(arr, left, right);
 QuickSort(arr, left, div - 1);
 QuickSort(arr, div + 1, right);
}

非遞歸實(shí)現(xiàn)快速排序

void QuickSort_NonR(int *arr, int left, int right)//快速排序---非遞歸法(利用棧)
{
 assert(arr);
 stack<int> s;
 if (left < right)//兩端數(shù)據(jù)入棧,right先入棧，left后入棧
 {
  s.push(right);
  s.push(left);
 }
 while (left < right && !s.empty())
 {
  //取出要進(jìn)行數(shù)據(jù)段的兩端
  left = s.top();
  s.pop();
  right = s.top();
  s.pop();
  if (left - right < 13)
  {
   InsertSort(arr, left - right + 1);
  }
  else
  {
      int div = PartSort3(arr, left, right);//循環(huán)進(jìn)行，div的右邊后入棧，先進(jìn)行右邊的排序
   if (left < div - 1)
   {
    s.push(div - 1);
    s.push(left);
   }
   if (right > div + 1)
   {
    s.push(right);
    s.push(div + 1);
   }
  }
 }
}

● 歸并排序（Merg Sort）

1、算法描述：

     歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個(gè)非常典型的應(yīng)用

2、步驟：

1）申請(qǐng)和原序列一樣大的空間，該空間用來(lái)存放合并后的序列

2）序列分為兩部分，進(jìn)行遞歸，先使小的序列有序，在回退使較大序列有序

3）進(jìn)行兩個(gè)序列的合并后，將有序序列回寫(xiě)到原序列中

具體實(shí)現(xiàn)如下：

void _Merg(int *arr, int *tmp, int begin1, int end1, int begin2, int end2)//進(jìn)行兩個(gè)序列的合并
{
 assert(arr);
 assert(tmp);
 int index = begin1;
 while (begin1 <= end1 && begin2 <= end2)
 {
  if (arr[begin1] < arr[begin2])//小的數(shù)據(jù)寫(xiě)入tmp
  {
   tmp[index] = arr[begin1];
   begin1++;
  }
  else
  {
   tmp[index] = arr[begin2];
   begin2++;
  }
  index++;
 }
 //數(shù)據(jù)多序列的鏈接在tmp后面
 while (begin1 <= end1)
 {
  tmp[index++] = arr[begin1++];
 }
 while (begin2 <= end2)
 {
  tmp[index++] = arr[begin2++];
 }
}
void _MergSort(int *arr, int *tmp, int left, int right)//遞歸使要進(jìn)行合并的序列有序，再調(diào)用合并序列函數(shù)
{
 assert(arr);
 assert(tmp);
 if (left >= right)
 {
  return;
 }
 int mid = left - (left - right) / 2;
 _MergSort(arr, tmp, left, mid);
 _MergSort(arr, tmp, mid + 1, right);
 //合并后回寫(xiě)到arr中
 _Merg(arr, tmp, left, mid, mid + 1, right);
 for (int i = left; i <= right; i++)
 {
  arr[i] = tmp[i];
 }
}
void MergSort(int *arr, int size)
{
 assert(arr);
 int *tmp = new int[size];//開(kāi)辟size空間tmp臨時(shí)存放部分合并的數(shù)據(jù)
 memset(tmp, 0, size*sizeof(int));//初始化
 _MergSort(arr, tmp, 0, size - 1);
 delete[] tmp;
}

對(duì)于這7種算法的復(fù)雜度和穩(wěn)定性的總結(jié)