今天开始复习一下排序，其实这个最近都有再捡起来练，毕竟太久远拿起来还挺不容易的。
简单说一下——自己复习排序的时候理解是这样的：基本的排序分为三类：交换排序、选择排序、插入排序。用一张图表示一下：
基本的排序
不得不说，我画的图简直太丑了......
将就看一下吧，大概是这样的。前面的话有点多了，直接进入今天的正题——交换排序。
冒泡排序：BubbleSort
冒泡排序应该是最简单的了吧？额，至少我个人觉得应该是最好理解的一种排序。
百度百科的原理：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
说起原理来感觉好难懂是吧？？？
其实可以简单去思考：为啥叫冒泡排序呢？
不知道有没有注意过水里的气泡，大的气泡会浮到上面去。冒泡排序也是：每一轮的排序,在这一轮中参与比较的元素中最大的数将会浮到最后。
时间复杂度之类的分析，我写在了备注中~~~
So,直接上代码：
请注意第二层for循环，循环次数会越来越小，简单思考一下就会发现：毕竟每轮过后相对来说最大的数都会排到应该在的地方去，所以如果再多比较那几次也没啥意义~
/**
* Created by AceCream on 2017/3/19.
* 冒泡排序BubbleSort（属于交换排序）
* 时间复杂度： 平均：O(n^2) 最佳：O(n) 最坏：O(n^2)
* 空间复杂度： O(1)
* 稳定性： 稳定
*/
public class BubbleSort {
public static void bubbleSort(int[] values){
for (int i=0;i<values.length;i++){
for (int j=i;j<values.length;j++){
if (values[i]>values[j]){
int temp = values[i];
values[i] = values[j];
values[j] = temp;
}
}
}
}
public static void main(String[] args) {
int value[] = {1,7,5,8,3};
bubbleSort(value);
for (int result : value) {
System.out.print(result+" ");
}
}
}
快速排序：Quicksort
为啥叫快速排序？因为他比别的排序快啊！当然这是一般情况下，也就是平均情况下，快速排序的时间复杂度是O(nlogn)，这速度真的不要太快！
！！！但是！！！
“快速排序是最快的排序”，这句话是正确的吗？？？
答案是：“不准确！”
因为按照平均速度来说，它确实很快，但是如果“枢纽元”为最大或者最小数字，那这个时候简直就是灾难！对！灾难！它就直接成为了——冒泡排序（Ps：冒泡：“靠！这个锅，我不背！”）
具体这个“枢纽元”是啥？还是从快速排序的原理说起来：
快排原理
原理：
- 确定一个基准值
- 一次循环：从后往前比较，用基准值和最后一个值比较，
- 如果比基准值小的交换位置，如果没有继续比较下一个，
- 直到找到第一个比基准值小的值才交换。
- 找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，
- 如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。
- 直到从前往后的比较索引>从后往前比较的索引，结束第一次循环。
- 此时，对于基准值来说，左右两边就是有序的了。
- 接着分别比较左右两边的序列，重复上述的循环。
行了，看了原理，我相信基本上都懵逼了，我当初也是被快排折磨是不行，找了大量的文档，没看懂。后来自己每一步都在纸上写一遍，终于发现了其精髓所在！
简单来说，快速排序其实是冒泡排序的加强版！从成熟体化身为完全体！至于究极体，还得在其基础上继续优化~~
我们第一次循环中，确定的这个“基准值”，就是上文所述的“枢纽元”。
借用一下百科的图片：
快速排序
这个图挺好，但是“初始”和“一次划分”中间省略了很多步，我来补充一下：想象一下挖坑~
1.首先把第一个值，也就是49作为key值，取出来存坑里
2.从右边开始向左边，依次和key值比较，一旦发现比它小的了也就是27，就把27挖出来，填在它曾经的坑里(第一个位置)。这时候变成了这个样子：
27，38，65，97，76，13，27，49
3.那么这时候，出现了俩27，这第二个27，人已经走了，但是它的坑还在，很尴尬，咋办？我们继续走下一步，从左边开始比较(注意！就不要从第一个开始了，已经比较完了，就从38开始吧)，比较谁？还是依次与key(49)比较，直到发现比key大的数，也就是65，这时候就把65，放到刚刚那个尴尬的坑里，把“坑里的值”更新掉~于是变成了这样：
27，38，65，97，76，13，65，49
然后把最开始挖出来的那个49填坑里
27，38，49，97，76，13，65，49
但是这样就结束第一此划分了吗？并没有，因为从start开始的left值和end开始的right值，还没有碰到一起(left<right),所以继续走，重复刚才的动作，直到他们相遇，这个时候：49左边的数都小于49，右边的数都大于或等于49。也就完成了第一次划分。
这之后我们看一下上面的图，以49为中心，分成了两个部分，这里就体现了“分治”的思想。将一个问题，分解成两个小的部分，分别做相同的操作。将两个部分做同样的操作，你想到了什么方式？对！递归！快速排序，体现了算法的两大思想：递归和分治。所以快速排序才这么重要。
这里多说一句，前面说过如果这个"枢纽元"选的不好，那就很尴尬了，比如说，这组数，我第一个值如果不是49而是13呢？那第一次划分后，13放在了最左边，我们再看第二个值，如果第二个值是27呢？以此类推，如果我的这串数字刚开始就比较有序，那么快排反而成为了冒泡啊！时间复杂度变为了N(n^2)，所以说，快速排序并不稳定。
但是！我们不能因为这个就否定它，毕竟在大量的测试中，快速排序的速度是要优与堆排序和shell排序的。
是不是听起来很晕。自己动手（请在纸上）写一遍流程其实就懂得了~~
接下来，直接手敲代码：
/**
* Created by AceCream on 2017/3/19.
* 快速排序QuickSort （属于交换排序）
* 原理：
* 一次循环：从后往前比较，用基准值和最后一个值比较，
* 如果比基准值小的交换位置，如果没有继续比较下一个，
* 直到找到第一个比基准值小的值才交换。
* 找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，
* 如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。
* 直到从前往后的比较索引>从后往前比较的索引，结束第一次循环。
* 此时，对于基准值来说，左右两边就是有序的了。
* 接着分别比较左右两边的序列，重复上述的循环。
*
* 时间复杂度： 平均：O(nlog2n) 最佳：O(nlog2n) 最坏：O(n^2)
* 空间复杂度： O(1)
* 稳定性： 不稳定
*
*/
public class QuickSort {
private static void quickSort(int[] value, int start, int end) {
int left = start;
int right = end;
int key = value[start];
while (left<right){
while (left<right&&value[right]>=key){
right--;
}
if (left<right){
value[left] = value[right];
left++;
}
while (left<right&&value[left]<key){
left++;
}
if (left<right){
value[right] = value[left];
right--;
}
value[left] = key;
if (left>start) quickSort(value,start,left-1);
if (right<end) quickSort(value,right+1,end);
}
}
public static void main(String[] args) {
int[] value = {49,38,65,97,76,13,27,49};
int start = 0;
int end = value.length-1;
quickSort(value,start,end);
//打印出来
for (int result : value) {
System.out.print(result+" ");
}
}
}
网友评论