快速排序(Quick Sort)算法原理及实现

参考：快速排序 原理：在数列里面找到一个基准值，凡是比这个基准值大的都移动到它前面（假设升序排列），比它大的移动到后面。这样就找到了这个基准值应该在的位置。同理，对基准值左右两侧的数列进行同样处理，直到排序完成。 平均时间复杂度为$O(nlogn)$，在最糟的情况下需要$O(n^2)$ 举例： 选取6作为基准值，确定6在数列中的位置 用两个指针分别指向左端和右端(left, right)。刚开始，让右端right移动，直到right指向的值小于基准值6，也就是4的位置；而后left移动，直到left指向的值大于6，即10的位置，之后两个值交换 之后继续按上述规则移动 交换两个值 直到right = left + 1 然后交换基准值和此时left位置的值，这时候基准值的位置就是其在序列中应在的位置 然后对基准值左右两侧的子序列进行同样的操作，直到排序完成。

参考代码

def swap(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp def Quick_Sort(arr, left, right): if left > right: return base = arr[left] [left_t, right_t] = [left, right] while left_t < right_t: #移动右侧指针 while arr[right_t] >= base and right_t > left_t: right_t = right_t - 1 #移动左侧指针 while arr[left_t] <= base and right_t > left_t: left_t = left_t + 1 swap(arr, left_t, right_t) swap(arr, left, left_t) #两侧子序列递归 Quick_Sort(arr, left, left_t - 1) Quick_Sort(arr, right_t + 1, right)

测试

arr = [10, 2, 5, 9, 15, 21, 13, 0, 19, 27, 16] if __name__ == '__main__': Quick_Sort(arr, 0, len(arr) - 1) print(arr)

C++

void Quick_sort(int arr[], int left, int right) { int mid = left; for (int i = left; i < right; i++) { if (arr[i] < arr[right]) { std::swap(arr[i], arr[mid]); mid ++; } } std::swap(arr[right], arr[mid]); if (mid > left + 1) { Quick_sort(arr, left, mid - 1); } if (mid < right - 1) { Quick_sort(arr, mid + 1, right); } }