溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例為大家分享了C/C++實現雙路快速排序算法的具體代碼，供大家參考，具體內容如下
看了劉宇波的視頻，講雙路快速排序的，原理講的很直觀，程序講解也一看就懂。這里寫一下自己的理解過程，也加深一下自己的理解。
首先說一下為什么需要雙路排序，在有些帶有許多重復數據的數組里，使用隨機快速排序或者最簡單的快速排序算法時，由于重復的數據會放在原來的索引位置不動，就回導致劃分數組時劃分的某一部分太長，起不到分段排序的效果，這樣就導致算法退化成O(n^2)的復雜度。就像下圖：
為了解決這個問題，雙路快速排序采用的方法是對等于v的數也進行交換，原理如下所述：
首先選擇一個數作為標志，放在數組的最左側，下標為l，在數組左邊放小于v的數，右側放大于v的數。
之后，先從l+1開始遍歷數組，當數據小于v時，該數據屬于左側橙色部分，保持其位置不動，i++,繼續向后遍歷，當找到某個數大于或者等于（注意，這里等于很重要）v時，停止遍歷。轉而開始根據j來遍歷數組，j不斷減小，索引數組的數據，當索引到某個數小于或者等于v時，停止遍歷。如下圖所示：
這時兩個綠色的區域就是分別屬于<v和>v的部分，而i,j所對應的索引數據要交換位置。
之后，將i,j分別向后向前移動一位，繼續開始新的索引，直到i和j重合或者i>j位置，就完成了partition的過程。
下面貼出代碼：
主函數 main.cpp
// QuickSort2.cpp : 雙路快速排序，適用于解決有很多重復數據的數組。
//
#include "stdafx.h"
#include "E:/學習/C++/數據結構和算法/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)
{
//此處結合隨機快速排序的算法進行了優化，標記點在數組里隨機選擇
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)
{
//選擇開頭的數作為分割的數
int RAND = arr[rand() % (r - l + 1) + l];
swap(arr[l], RAND);
int i = arr[l];
//遍歷數組，使得arr[l,l+1,...j]<arr[l],arr[j+1,...,k)>arr[l]
int j = l;
//如果當前數據大于arr[l]，就無需改變位置，如果小于arr[l]，就將當前數據與分割點的數據后一個數據交換
for (size_t k = j + 1; k <= r; k++)
{
if (arr[k]<i)
{
swap(arr[j + 1], arr[k]);
j++;
}
}
//最后一步，要記得將arr[l]和找到的分割點數據交換
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)
{
//選擇開頭的數作為分割的數
int i = arr[l];
//遍歷數組，使得arr[l,l+1,...j]<arr[l],arr[j+1,...,k)>arr[l]
int j = l;
//如果當前數據大于arr[l]，就無需改變位置，如果小于arr[l]，就將當前數據與分割點的數據后一個數據交換
for (size_t k = j + 1; k <= r; k++)
{
if (arr[k]<i)
{
swap(arr[j + 1], arr[k]);
j++;
}
}
//最后一步，要記得將arr[l]和找到的分割點數據交換
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 函數
#ifndef SORTTESTHELPER_H
#define SORTTESTHELPER_H
#include <iostream>
#include <cassert>
#include <ctime>
#include <string>
using namespace std;
namespace SortTestHelper
{
//產生一個從[rangeL,rangeH]的隨機數組，數組個數是n
int* generateRadomArray(int n,int rangeL,int rangeH)
{
//為了算法的健壯性，需要判斷錯誤輸入
assert(rangeL < rangeH);
int* arr = new int[n];
//時間為種子的隨機數
srand((unsigned)time(NULL));
for (int i = 0;i < n;i++)
{
//生成rangeL到rangeH之間的隨機數的算法
arr[i] = rand() % (rangeH - rangeL + 1) + rangeL;
}
return arr;
}
//產生近乎有序的隨機數
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;
}
//打印數組：輸入數組，數組元素的個數
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;
}
//判斷是否已經排序
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>
//函數輸入參數是：所需要計算的運行的函數的名稱，函數的指針，函數的輸入數組，輸入數組的個數
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;
}
//拷貝隨機生成的數組:輸入要拷貝的數組指針(整型)，輸入需要拷貝多少個數
int* copyarr(int* a, int n)
{
int *arr = new int[n];
copy(a,a+n, arr);
return arr;
}
}
#endif
最終結果三種算法對10萬個具有重復的數據的排序時間如下：
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
