排序算法系列(1)——快速排序
前几天被一哥们儿实力嘲讽，问我快速排序怎么实现，我只是记得自己学过，但是忘记了具体怎么实现，原理是什么ORZ，然后LL就努力去百度学习，汲取，大致将一些自己的感受：
注意！文档只是以我的想法来进行阐述，只是尽量以我能理解的方式来解释算法原理，只是为了将来上了年纪，或者忘记了这个原理的时候来学习一下。
废话不多说，套用之前那哥们讲话，冒泡是最简单的排序方法
那么接下来
讲一下快速排序
情景拟定：
一个数组array，需要将其从由小到大的顺序排列
array = { 4 , 5 , 2 , 22 , 11 , 32 , 2 , 5 }
快速排序的原理是这样子的：
分治的原理：
首先选定一个元素a，然后将这个数组中比这个元素小的元素们放到该元素的左边，将数组中比这个元素大的元素放到该元素的右边。 至此a元素的位置已经排好了，剩下的就是由a将数组划成两半进行排序
每一半排序方式同上。
这样子最后肯定能排好序
明显能够看出这是**递归**的思想
然后问题来了，首先怎么具体的将a放到他应该的位置？
是这样子的
/(比较方便，确保了只是将除了该a之外的其余数字只比较一遍)→往下看就能理解我这句话了/
首先我们需要给这个数组定义一个首、尾index，比如 i=0，j=array.length-1=7;
假定我们需要排的元素 a=array[0]=4
那么首先我们从array[j]处向前遍历比较
array[7]=5>4 正常 j--
array[6]=2<4 应该在4左边，所以将array[0]=2
此时 j = 6 ；
array现在是这样子的 array = {2 , 5 , 2 , 22 , 11 , 32 , 空 ,5}
那么现在array[6] (也就是array[j]) 空出来了
我们这时候应该看一下i往后了
array[0] < a 正常 i++
array[1] = 5 > a 不对哦 比4大应该在右边
所以将5放到刚才上面缺的地方
array[j] = 5
那么现在是array = {2,空,2,22,11,32,5,5}
i = 1
现在array[1] 也就是array[i] 空了
接下来接着从j的位置向前
array[6] = 5 < 4 okay j--
array[5] = 32 >4 okay j--
array[4] = 11 > 4 okay j--
array[3] = 22 > 4 okay j--
array[2] = 2 < 4 换换换
array[i] = array[1] = 2
那么现在 j 为2了，
array = {2,2,空,22,11,32,5,5}
再从i开始
i=1
array[i] = 2 < 4 okay i++
此时 i=2=j 交头了说明over了
那么将刚才最开始的a 放到array[i] or array[j]位置上就好了 (反正 i 和 j 相等了)
array = {2,2,4,22,11,32,5,5}
那么接下来需要对array的两个子串
array1={2,2}
array2={22,11,32,5,5}
然后对子串进行像刚才那样的顺序排序
package quickSort;
import java.util.Arrays;
/**
* 递归实现快速排序
* @author mengf
*
*/
public class Qsort {
public static int[] quickSort(int[] array,int start , int end){
int i = start;
int j = end;
int a = array[i];
//好的情况
while (i!=j&&i<j) {
while (j!=i) {
if (array[j]<a) {
array[i]=array[j];
i++;
break;
}else{
j--;
}
}
while (j!=i) {
if (array[i]>a) {
array[j]=array[i];
j--;
break;
}else{
i++;
}
}
}
//然后最后i=j
array[i]=a;
//分成两半
if (i>start) {
quickSort(array, start, i-1);
}
if (i<end) {
quickSort(array, i+1, end);
}
return array;
}
public static void main(String[] args) {
int[] array = {12,10,22,5,6,8,11,7,3,4,5,33,32,23,34,32,43,34};
quickSort(array, 0, array.length-1);
System.out.println(Arrays.toString(array));
}
}
所以不难看出如果要实现递归实现是很好理解的
注：如果有大神看到这里肯定会觉得我上面写的有些问题
我承认我顺着思路写完之后其实有地方需要改进的
！就是需要替换的时候，比如j往前跟4对比，遇到需要替换的时候，将array[i]替换之后，可以将i++
因为替换到i位置上肯定已经满足这个数字<4 所以将i++之后
从i这边开始的时候就不需要重新再将刚替换的位置的数字和a再比较了。
下面开始看一下递归的java代码实现：
然后后来百度了一下百科是这样写的，原理是一样的
package quickSort;
import java.util.Arrays;
public class QuickSort {
/**
* 无边界检查
* 完全专注于算法
* @param arrays
* @param start
* @param end
* @return
*/
public int[] quickSort(int[] arrays,int low,int high){
int start = low;
int end = high;
//只有一个元素的时候是排好序的了
if (start==end) {
return arrays;
}
//算法开始
int temp = arrays[start];
while (start<end) {
while (start<end && arrays[end]>=temp) {
end--;
}
arrays[start]=arrays[end];
while (start<end && arrays[start]<=temp) {
start++;
}
arrays[end]=arrays[start];
}
//start = end
arrays[start]=temp;
//迭代两边排序
if (start>low) {
quickSort(arrays, 0, start-1);
}
if (end<high) {
quickSort(arrays,start+1,arrays.length-1);
}
return arrays;
}
public static void main(String[] args) {
QuickSort quickSort = new QuickSort();
int[] arrays = {1,11,35,2,3,5,323,213,22,3,1,2,3,4,5,3};
quickSort.quickSort(arrays, 0, arrays.length-1);
System.out.println(Arrays.toString(arrays));
}
}
臭美一下，我觉得这个大概就是我之前没有在换位置之后将对应的位置的 i++或者 j-- 这样感觉会多一次判断，虽然对算法复杂度没有影响。
再就是如果加上了的话这个写法比我写的好多了，判断写在while里面
而我的是while中又有if，感觉效率没有这个高。
算法复杂度: O(n*logn)
但是写到这里，我有问题了
递归对伐，大家都知道浪费空间的做法，但是递归对于程序的理解有着极大的帮助，而且我记得数据结构老师说过，所有的递归都能改为循环的，这就是对于这个问题的下一步探讨了，我先学习下，等搞懂了再搞一篇优化后的快速排序。
现在说说我觉得这样的<u>局限</u>在哪里：
如果排序对象较大，数目较多，内存可能不够，虽然很少有出现这种情况，但是如果能够改成循环，而放弃递归
无疑是对能力的提升，像我这种懒人还是觉得递归好，起码理解起来简单，至于循环，最近看情况找找资料学学，要是没有下一篇了的话，可能LL已经忘记这件事情了，大家可以先用着递归，毕竟现在普通项目中也不太可能遇到占用很大内存来递归的情况。
