C/C++實現(xiàn)雙路快速排序算法原理

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C語言|點擊：次

本文實例為大家分享了C/C++實現(xiàn)雙路快速排序算法的具體代碼，供大家參考，具體內(nèi)容如下

看了劉宇波的視頻，講雙路快速排序的，原理講的很直觀，程序講解也一看就懂。這里寫一下自己的理解過程，也加深一下自己的理解。

首先說一下為什么需要雙路排序，在有些帶有許多重復數(shù)據(jù)的數(shù)組里，使用隨機快速排序或者最簡單的快速排序算法時，由于重復的數(shù)據(jù)會放在原來的索引位置不動，就回導致劃分數(shù)組時劃分的某一部分太長，起不到分段排序的效果，這樣就導致算法退化成O(n^2)的復雜度。就像下圖：

為了解決這個問題，雙路快速排序采用的方法是對等于v的數(shù)也進行交換，原理如下所述：

首先選擇一個數(shù)作為標志，放在數(shù)組的最左側，下標為l，在數(shù)組左邊放小于v的數(shù)，右側放大于v的數(shù)。
之后，先從l+1開始遍歷數(shù)組，當數(shù)據(jù)小于v時，該數(shù)據(jù)屬于左側橙色部分，保持其位置不動，i++,繼續(xù)向后遍歷，當找到某個數(shù)大于或者等于（注意，這里等于很重要）v時，停止遍歷。轉而開始根據(jù)j來遍歷數(shù)組，j不斷減小，索引數(shù)組的數(shù)據(jù)，當索引到某個數(shù)小于或者等于v時，停止遍歷。如下圖所示：

這時兩個綠色的區(qū)域就是分別屬于<v和>v的部分，而i,j所對應的索引數(shù)據(jù)要交換位置。

之后，將i,j分別向后向前移動一位，繼續(xù)開始新的索引，直到i和j重合或者i>j位置，就完成了partition的過程。

下面貼出代碼：

主函數(shù) main.cpp

// QuickSort2.cpp : 雙路快速排序，適用于解決有很多重復數(shù)據(jù)的數(shù)組。
//

#include "stdafx.h"
#include "E:/學習/C++/數(shù)據(jù)結構和算法/code/算法/排序算法/common/sortTestHelper.h"
#include "QuickSort.h"
#include "RadomQuickSort.h"
#include "QuickSort2.h"

using namespace std;

int main()
{
 int n = 100000;
 int *arr1 = SortTestHelper::generateRadomArray(n, 0, 50);
 int *arr2 = SortTestHelper::generateRadomArray(n, 0, 50);
 int *arr3 = SortTestHelper::generateRadomArray(n, 0,50);
 SortTestHelper::sortTime("隨機快速排序", RadomQuickSort, arr1, n);
 SortTestHelper::sortTime("快速排序", QuickSort, arr2, n);
 SortTestHelper::sortTime("雙路快速排序", QuickSort2, arr3, n);
 delete[] arr1;
 delete[] arr2;
 delete[] arr3;
 return 0;
}

雙路快速排序算法 QuickSort2.h

#ifndef QUICKSORT2_H
#define QUICKSORT2_H

#include <stdlib.h>
#include <iostream>
using namespace std;

template <typename T>
int __partition3(T *arr, int l, int r)
{
//此處結合隨機快速排序的算法進行了優(yōu)化，標記點在數(shù)組里隨機選擇
 int RAND = (rand() % (r - l + 1) + l);
 swap(arr[RAND], arr[l]);

 int v = arr[l];
 int i = l + 1;
 int j = r;
 while (true)
 {
 while (i <= r&&arr[i] < v) i++;
 while (j >= l + 1 && arr[j] > v) j--;
 if (i > j)
 {
 break;
 }
 swap(arr[i], arr[j]);
 i++;
 j--;
 }
 swap(arr[l], arr[j]);
 return j;
}

template <typename T>
void __QuickSort2(T *arr,int l,int r)
{
 if (l>=r)
 {
 return;
 }
 int p = __partition3(arr, l, r);
 __QuickSort2(arr, l, p - 1);
 __QuickSort2(arr, p + 1, r);
}

template <typename T>
void QuickSort2(T *arr, int n)
{
 __QuickSort2(arr, 0,n-1);
}


#endif

隨機快速排序 RadomQuickSort.h

#ifndef RADOMQUICKSORT_H
#define RADOMQUICKSORT_H

#include <iostream>
#include <stdlib.h>

using namespace std;

template <typename T>
int __Randpartition(T *arr, int l, int r)
{
 //選擇開頭的數(shù)作為分割的數(shù)
 int RAND = arr[rand() % (r - l + 1) + l];
 swap(arr[l], RAND);
 int i = arr[l];
 //遍歷數(shù)組，使得arr[l,l+1,...j]<arr[l],arr[j+1,...,k)>arr[l]
 int j = l;
 //如果當前數(shù)據(jù)大于arr[l]，就無需改變位置，如果小于arr[l]，就將當前數(shù)據(jù)與分割點的數(shù)據(jù)后一個數(shù)據(jù)交換
 for (size_t k = j + 1; k <= r; k++)
 {
 if (arr[k]<i)
 {
 swap(arr[j + 1], arr[k]);
 j++;
 }
 }
 //最后一步，要記得將arr[l]和找到的分割點數(shù)據(jù)交換
 swap(arr[l], arr[j]);
 return j;
}

template <typename T>
void __RadomQuickSort(T *arr, int l, int r)
{
 if (l >= r)
 {
 return;
 }
 int p = __Randpartition(arr, l, r);
 __RadomQuickSort(arr, l, p - 1);
 __RadomQuickSort(arr, p + 1, r);
}

template <typename T>
void RadomQuickSort(T *arr, int n)
{
 __RadomQuickSort(arr, 0, n - 1);
}

#endif

快速排序 QuickSort.h

#ifndef QUICKSORT_H
#define QUICKSORT_H

using namespace std;

template <typename T>
int __partition(T *arr, int l, int r)
{
 //選擇開頭的數(shù)作為分割的數(shù)
 int i = arr[l];
 //遍歷數(shù)組，使得arr[l,l+1,...j]<arr[l],arr[j+1,...,k)>arr[l]
 int j = l;
 //如果當前數(shù)據(jù)大于arr[l]，就無需改變位置，如果小于arr[l]，就將當前數(shù)據(jù)與分割點的數(shù)據(jù)后一個數(shù)據(jù)交換
 for (size_t k = j + 1; k <= r; k++)
 {
 if (arr[k]<i)
 {
 swap(arr[j + 1], arr[k]);
 j++;
 }
 }
 //最后一步，要記得將arr[l]和找到的分割點數(shù)據(jù)交換
 swap(arr[l], arr[j]);
 return j;
}

template <typename T>
void __QuickSort(T *arr, int l, int r)
{
 if (l >= r)
 {
 return;
 }
 int p = __partition(arr, l, r);
 __QuickSort(arr, l, p - 1);
 __QuickSort(arr, p + 1, r);
}

template <typename T>
void QuickSort(T *arr, int n)
{
 __QuickSort(arr, 0, n - 1);
}

#endif

SortTestHelper 函數(shù)

#ifndef SORTTESTHELPER_H
#define SORTTESTHELPER_H

#include <iostream>
#include <cassert>
#include <ctime>
#include <string>

using namespace std;

namespace SortTestHelper 
{
//產(chǎn)生一個從[rangeL,rangeH]的隨機數(shù)組，數(shù)組個數(shù)是n
 int* generateRadomArray(int n,int rangeL,int rangeH)
 {
 //為了算法的健壯性，需要判斷錯誤輸入
 assert(rangeL < rangeH);
 int* arr = new int[n];
 //時間為種子的隨機數(shù)
 srand((unsigned)time(NULL));
 for (int i = 0;i < n;i++)
 {
 //生成rangeL到rangeH之間的隨機數(shù)的算法
 arr[i] = rand() % (rangeH - rangeL + 1) + rangeL;
 }
 return arr;
 }

//產(chǎn)生近乎有序的隨機數(shù)
 int *generateNearlyOrderedArray(int n, int swapnum)
 {
 int *arr = new int[n];
 srand((unsigned)time(NULL));
 for (size_t i = 0; i < n; i++)
 {
 arr[i] = i;
 }
 for (size_t i = 0; i < swapnum; i++)
 {
 int x = rand() % n;
 int y = rand() % n;
 swap(arr[x], arr[y]);
 }
 return arr;
 }

//打印數(shù)組：輸入數(shù)組，數(shù)組元素的個數(shù)
 template<typename T>
 void printArr(T *arr,int n)
 {
 for (size_t i = 0; i < n; i++)
 {
 std::cout << arr[i] << " ";
 }
 std::cout << std::endl;
 }

//判斷是否已經(jīng)排序
 template<typename T>
 bool ifSort(T *arr,int n)
 {
 for (size_t i = 0; i < n-1; i++)
 {
 if (arr[i]>arr[i+1])
 {
 return false;
 }
 }
 return true;
 }

//計算程序運行時間
 template<typename T>
 //函數(shù)輸入?yún)?shù)是：所需要計算的運行的函數(shù)的名稱，函數(shù)的指針，函數(shù)的輸入數(shù)組，輸入數(shù)組的個數(shù)
 void sortTime(string funName,void(*sort)(T*arr, int), T* arr,int n)
 {
 clock_t startime = clock();
 sort(arr,n);
 clock_t endtime = clock();

 assert(ifSort(arr, n));
 std::cout <<funName<<"的運行時間：" << double(endtime-startime) / CLOCKS_PER_SEC <<"s"<< std::endl;
 }

//拷貝隨機生成的數(shù)組:輸入要拷貝的數(shù)組指針(整型)，輸入需要拷貝多少個數(shù)
 int* copyarr(int* a, int n)
 {
 int *arr = new int[n];
 copy(a,a+n, arr);
 return arr;
 }
}
#endif

最終結果三種算法對10萬個具有重復的數(shù)據(jù)的排序時間如下：

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持我們。

上一篇：Opencv圖像處理之輪廓外背景顏色改變

欄目：C語言

下一篇：Opencv實現(xiàn)圖像灰度線性變換

本文標題：C/C++實現(xiàn)雙路快速排序算法原理

本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/288.html

更多C語言

欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

C語言

C/C++實現(xiàn)雙路快速排序算法原理

您可能感興趣的文章

閱讀排行

本欄相關

隨機閱讀