快速排序是一种经常用到的排序方法,它的时间复杂度为 O(nlogn)。因为大多数情况下速度都比一般的排序方法快,用的比较多,自己就琢磨着实现了一下。
原理
快速排序用到了分治法的原理:
从数组中随机取出一个数字,将这个数组分为两个部分。将取出的数字作为基准数,小于基准数的放到它的左边,大于基准数的放到它的右边。这样基准数左边的都是比它小的,右边的都是比它大的。然后再对基准数的左边和右边重复前面的过程,直到每个部分的数组长度为 1。最后再将这些分开的数组组合起来就成功了。步骤如下:
- 从数组中随机抽取一个数组作为基准数,将数组中的每个数字与基准数比较,小于基准数的放到基准数左边,大于基准数的放到基准数右边。
- 对上面结束后的左右两个部分重复步骤 1。
- 当所有部分的长度为 1 时停止。
实现
下面是自己熟悉的语言的实现(用第一个数作为基准数,并且采用递归的方法):
Python 版本
def quick_sort(lst,left,right): truei = left; truej = right trueif i >= j: truetruereturn lst truek = lst[i] truewhile i < j: truetruewhile i < j and lst[j] >= k: truetruetruej -= 1 truetruelst[i] = lst[j] truetruewhile i < j and lst[i] <= k: truetruetruei += 1 truetruelst[j] = lst[i] truelst[i] = k truequick_sort(lst,left,i-1) truequick_sort(lst,j+1,right) truereturn lst
|
JavaScript 版
function quick_sort(lst, l, r) { var i = l, j = r, k = lst[l]; if (i >= j) { return lst; } while (i < j) { for (; i < j; j--) { if (lst[j] <= k) { lst[i] = lst[j]; i++; break; } } for (; i < j; i++) { if (lst[i] >= k) { lst[j] = lst[i]; j--; break; } } } lst[i] = k; quick_sort(lst, l, i - 1); quick_sort(lst, j + 1, r); return lst; }
|
C 语言版
void qucik_sort(int lst[],int l,int r) { trueif(l < r) true{ truetrueint i = l, j = r, k = lst[l]; truetruewhile (i < j){ truetruetruefor (; i < j; --j) truetruetrue{ truetruetruetrueif (lst[j] <= k) truetruetruetrue{ truetruetruetruetruelst[i] = lst [j]; truetruetruetruetruei++; truetruetruetruetruebreak; truetruetruetrue} truetruetrue} truetruetruefor (; i < j; ++i) truetruetrue{ truetruetruetrueif (lst[i] >= k) truetruetruetrue{ truetruetruetruetruelst[j] = lst[i]; truetruetruetruetruej--; truetruetruetruetruebreak; truetruetruetrue} truetruetrue} truetrue} truetruelst[i] = k; truetruequcik_sort(lst, l, i-1); truetruequcik_sort(lst, j+1, r); true} }
|