1.原理
Quick Sort 属于交换排序,是对冒泡算法进行的改造。
基本原理:分治法和填坑法
- 分治法:
- 首先将问题转化为子问题,取数组的第一个元素key,然后将数组里的所有元素小于key的放在左边,大于key的放在右边。
- 此时再次重复这个过程,去小于key的元素,取第一个元素key2,然后将数组的所有元素小于key2的放在左边,大于key2的放在右边。
- 再次重复.......直到全部排序好。
- 填坑法
- 用于数组排序,取第一个元素key,然后将a[0]空出来,然后i=0,j=n。
- 设置大循环,保证i<j。
- 设置子循环,从后往前找,如果大于key就执行j--。
- 设置判定语句,如果小于key,将a[j]的值填入a[i]。
- 设置子循环,从前往后找,如果小于key就执行j++。
- 设置判定语句,如果大于key,就将a[i]的值填入a[j]。
- 大循环结束,将key值填入a[i]。
-
填坑法第一步,设值,key,i,j
-
从后往前第一次小循环
-
从前往后第一次小循环
-
从后往前第二次小循环
-
结束大循环,将key值填入a[i]。
2.java写法
- 分为两部分:分治递归quicksort和partition方法。
实现填坑法partition():
private static int partition(int a[], int i, int j) {
int key = a[i];//key值
while (i < j) {
while (i < j && a[j] > key)// 从右向左小循环
j--;
if (a[j] <= key)//判定填充
a[i] = a[j];
while (i < j && a[i] < key)// 从左向右小循环
i++;
if (a[i] >= key)//判定填充
a[j] = a[i];
}
a[i] = key;// 把轴元素放在轴所在地位置
return i;// 返回轴所在的位置
}
实现递归的quicksort():
private void quickSort(int data[], int low, int high) {// 递归
int q;
if (low < high) {
q = partition(data, low, high);
quickSort(data, q + 1, high);//对q左边进行分类
quickSort(data, low, q - 1);//对q右边进行分类
}
}
3.时间复杂度
-
对于划分成子问题求解的问题,公式为:
T(n) = a*T(n/b)+f(n) -
最好的情况,每次划分都是按照折半划分,快排的a=b=2,f(n)为partition()的规模。公式为:
T(n) = 2*T(n/2)+f(n)
例如 3,2,4。
复杂度为T(n) = O(nlogn) -
最坏的情况,每次划分都是:
T(n) = T(n-1)+T(1)+f(n)
例如 2,3,4。
复杂度为T(n) = O(n^2)
网友评论