資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：對大量元素進行快速排序
快速排序技術透過將列表分成兩部分來完成。最初，透過分割槽演算法選擇一個樞軸元素。樞軸的左邊部分包含小於樞軸的值，右邊部分包含大於樞軸的值。分割槽後，使用相同的過程對每個單獨的列表進行分割槽。
這裡我們考慮一個大型陣列（大約100個元素）進行排序。我們取一些數字，然後以隨機順序打亂它們，使它們無序。然後使用快速排序技術進行排序。
快速排序技術的複雜度
時間複雜度 - 最佳情況和平均情況為 O(n log n)，最壞情況為 O(n2)。
空間複雜度 - O(log n)
輸入 - 未排序列表：90 45 22 11 22 50
輸出 - 排序後陣列：11 22 22 45 50 90
演算法
partition(array, lower, upper)
輸入 - 資料集陣列、下界和上界
輸出 - 樞軸在正確的位置
Begin pivot := array[upper] i := lower – 1 for j in range lower to higher, do if array[j] < pivot, then exchange the values of array[i] and array[j] i := i + 1 done exchange the values of array[upper] and array[i + 1] return i + 1 End
quickSort(array, left, right)
輸入 - 一個數據陣列，以及陣列的下界和上界
輸出 - 已排序的陣列
Begin if lower < right then q = partition(array, left, right). quickSort(array, left, q-1) quickSort(array, q+1, right) End
示例程式碼
#include<iostream>
#include<cstdlib>
#include<ctime>
#define MAX 100
using namespace std;
void random_shuffle(int arr[]) { //function to shuffle the array elements into random positions
srand(time(NULL));
for (int i = MAX - 1; i > 0; i--) {
int j = rand()%(i + 1);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int partion(int arr[], int p, int r) {
int pivot = arr[r]; //last item as pivot
int i = p - 1;
for (int j = p; j < r; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i+1], arr[r]);
return i + 1;
}
void quick_sort(int arr[], int p, int q) { //recursively sort the list
int j;
if (p < q) {
j = partion(arr, p, q);
quick_sort(arr, p, j - 1);
quick_sort(arr, j + 1, q);
}
}
int main() {
int i;
int arr[MAX];
for (i = 0;i < MAX;i++)
arr[i] = i + 1;
random_shuffle(arr); //To randomize the array
quick_sort(arr, 0, MAX-1); //sort the elements of array
for (i = 0; i < MAX;i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}輸出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
更新於：2019年7月30日
354 次瀏覽
廣告