快速排序

特點(diǎn)：原址排序，最壞的時(shí)間復(fù)雜度O（n^2)
平均時(shí)間復(fù)雜度O（nlgn）
比歸并排序系數(shù)常數(shù)項(xiàng)小
不穩(wěn)定
底部有最壞時(shí)間復(fù)雜度為Ω(nlgn)的快速排序地址

void quick_sort(int *array,int start,int end); int partition(int *array,int start,int end);#include "quick_sort.h" void quick_sort(int *array,int start,int end){if(start<end){int k = partition(array,start,end);quick_sort(array,start,k-1);quick_sort(array,k+1,end);} } int partition(int *array,int start,int end){int key = array[end];int p = start - 1;int temp = 0;for (int i = start; i < end; ++i) {if(array[i] <= key){p++;temp = array[p];array[p] = array[i];array[i] = temp;}}array[end] = array[p+1];array[p+1] = key;return p+1; }

反向排序

int reverse_partition(int *array,int start,int end) {int p = start - 1;int key = array[end];for (int i = start; i < end; ++i) {if(array[i] >= key){p++;int temp = array[p];array[p] = array[i];array[i] = temp;}}array[end] = array[p+1];array[p+1] = key;return p+1; } void reverse_quick_sort(int *array,int start,int end){if(start<end){int k = reverse_partition(array,start,end);reverse_quick_sort(array,start,k-1);reverse_quick_sort(array,k+1,end);} }

Hoare 劃分的快速排序

int hoare_partition(int *array,int start,int end){int key = array[start];int left = start - 1;int right = end + 1;while (true){do {right -- ;} while (array[right]>key);do {left++;} while (array[left]<key);if(left<right){int temp = array[left];array[left] = array[right];array[right] = temp;} elsereturn right;} } void hoare_quick_sort(int *array,int start,int end) {if(start<end){int k = hoare_partition(array,start,end);hoare_quick_sort(array,start,k);hoare_quick_sort(array,k+1,end);} }

隨機(jī)劃分

int randomized_partition(int *array,int start,int end) {int random = random_include_left_right(start,end);int temp = array[end];array[end] = array[random];array[random] = temp;partition(array,start,end); }

隨機(jī)函數(shù)代碼

int random_include_left_right(int left,int right){srand((unsigned)time(NULL));return (rand() % (right - left +1))+ left; }

返回兩個(gè)參數(shù)的劃分 第一個(gè)到第二個(gè)數(shù)之間（包含）的數(shù)是等于主元素，并且第一個(gè)數(shù)前小于主元素，第二個(gè)數(shù)后是大于主元素

KeyValuePair partition_include_same_element(int *array,int start,int end) {int key = array[end];int left_line = start - 1;int equal_line = left_line;for (int i = start; i < end; ++i) {if(array[i] < key){left_line++;equal_line++;int temp = array[left_line];array[left_line] = array[i];array[i] = temp;}else if(array[i] == key){equal_line++;int temp = array[equal_line];array[equal_line] = array[i];array[i] = temp;}}array[end] = array[equal_line + 1];array[equal_line + 1] = key;equal_line++;return KeyValuePair(left_line+1,equal_line); } KeyValuePair randomized_partition_include_same_element(int *array,int start,int end){int random = random_include_left_right(start,end);int temp = array[random];array[random] = array[end];array[end] = temp;return partition_include_same_element(array,start,end); } void quick_sort_include_same_element(int *array,int start,int end){if(start<end){KeyValuePair keyValuePair = randomized_partition_include_same_element(array,start,end);quick_sort_include_same_element(array,start,keyValuePair.key-1);quick_sort_include_same_element(array,keyValuePair.value+1,end);} }

輔助類KeyValuePair 代碼鏈接

尾遞歸快速排序 時(shí)間復(fù)雜度在最壞的情況下保持O（nlgn）的時(shí)間復(fù)雜度

void tail_recursive_quick_sort(int *array,int start,int end) {while (start<end){int middle = partition(array,start,end);if(middle>(start+end)/2){tail_recursive_quick_sort(array,start,middle - 1);start = middle + 1;}else{tail_recursive_quick_sort(array,middle+1,end);end = middle - 1;}} }

時(shí)間復(fù)雜度為Ω(nlgn)的快速排序
代碼地址

總結(jié)

以上是生活随笔為你收集整理的算法-排序-快速排序(包含多种快速排序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。