1 冒泡排序（BubbleSort）
冒泡排序是排序算法中比较简单的了。
如果你没有接触过算法，给你一个乱序的数组，让你排序;
那么我们潜意识里面就会去找一个最大的或者最小的选出来，然后再在剩下的里面继续选一个最大的或者最小的，依次找下去，一直到最后一个。
那么这就是冒泡排序原理了。
冒泡排序的思路：
1. 遍历乱序数组，将最大的或者最小的选出来；
2. 按照同样的规则遍历剩下的乱序数组；
3. 直到遍历到最后一个；
思路清楚了，下面贴代码。
import java.util.Random;
/**
*
* @ClassName: BubbleSort
* @Description: 冒泡排序
* @author SNOOPY QQ:986619781
* @date 2017年3月20日 下午12:58:39
*
*/
public class BubbleSort {
private static int[] waitSort = new int[10];
public static void init() {
Random random = new Random();
for (int i = 0; i < waitSort.length; i++) {
waitSort[i] = random.nextInt(100);
}
}
public static void sortDisplay() {
for (int i = 0; i < waitSort.length; i++) {
System.out.print(waitSort[i] + " ");
}
System.out.println();
}
public static void bubbleSort() {
for (int i = 0; i < waitSort.length; i++) {
for (int j = 0; j < waitSort.length - i - 1; j++) {
if (waitSort[j] > waitSort[j + 1]) {
int temp = waitSort[j + 1];
waitSort[j + 1] = waitSort[j];
waitSort[j] = temp;
}
}
}
}
public static void main(String[] args) {
BubbleSort.init();
BubbleSort.sortDisplay();
BubbleSort.bubbleSort();
BubbleSort.sortDisplay();
}
}
算法分析
1. 算法的最好时间复杂度
若数组的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：
Cmin=n-1
Mmin=0。
冒泡排序最好的时间复杂度为O(n)。
2. 算法的最坏时间复杂度
若初始数组是反序的，需要进行n-1趟排序。
每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。
在这种情况下，比较和移动次数均达到最大值：
Cmax=n(n-1)/2=O(n2)
Mmax=3n(n-1)/2=O(n2)
冒泡排序的最坏时间复杂度为O(n2)。
（3）算法的平均时间复杂度为O(n2)
虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。
（4）算法稳定性
冒泡排序是就地排序，且它是稳定的。
2 快速排序（QuickSort）
快速排序是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。
2.1 算法思想
采用了一种分治的策略，通常称其为分治法
2.1.1 分治法的基本思想
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。
递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
2.1.2 快速排序的基本思想
* 从数列中挑出一个元素，称为 “基准”（pivot），
* 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
* 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
快排 - 引用自...我也忘了，反正不是我画的
2.2 上代码
import java.util.Random;
/**
*
* @ClassName: QuickSort
* @Description: 快速排序
* @author SNOOPY QQ:986619781
* @date 2017年3月22日 上午9:26:37
*
*/
public class QuickSort {
private static int[] waitSort = new int[10];
public static void init() {
Random random = new Random();
for (int i = 0; i < waitSort.length; i++) {
waitSort[i] = random.nextInt(100);
}
}
public static void sortDisplay() {
for (int i = 0; i < waitSort.length; i++) {
System.out.print(waitSort[i] + " ");
}
System.out.println();
}
public static void quickSort(int[] arrays, int left, int right) {
if (left < right) {
int i = division(arrays, left, right);
quickSort(arrays, left, i - 1);
quickSort(arrays, i + 1, right);
}
}
/**
*
* @Title: division/partition
* @Description: 分割
*
*/
public static int division(int[] arrays, int left, int right) {
// 基准
int pivot = arrays[left];
while (left < right) {
while (pivot <= arrays[right] && left < right) {
right--;
}
// 技巧：最左边的已经被当作基准，此位置可以看作废掉的位置，可以用来作为临时交换空间
arrays[left] = arrays[right];
while (pivot >= arrays[left] && left < right) {
left++;
}
arrays[right] = arrays[left];
}
arrays[left] = pivot;
return left;
}
public static void main(String[] args) {
QuickSort.init();
QuickSort.sortDisplay();
QuickSort.quickSort(waitSort, 0, waitSort.length - 1);
QuickSort.sortDisplay();
}
}
2.3 算法分析
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。
2.3.1 最坏时间复杂度
最坏情况是每次划分选取的基准都是当前无序区中关键字最小/最大的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。
因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：
Cmax = n(n-1)/2=O(n2)
如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。
2.3.2 最好时间复杂度
在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：
0(nlgn)
注意：
用递归树来分析最好情况下的比较次数更简单。
因为每次划分后左、右子区间长度大致相等，故递归树的高度为O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn)。
因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)。
2.3.3 基准关键字的选取
#在当前无序区中选取划分的基准关键字是决定算法性能的关键。#
① "三者取中"的规则
"三者取中"规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区伺的第1个记录进行交换，此后的划分过程与上面所给的Partition算法完全相同。
② 取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准
选取基准最好的方法是用一个随机函数产生一个取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准，这相当于强迫R[low..high]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序。
注意：
随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提高了，尤其是对初始有序的文件，一般不可能导致最坏情况的发生。算法的随机化不仅仅适用于快速排序，也适用于其它需要数据随机分布的算法。
2.3.4 平均时间复杂度
尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
2.3.5 空间复杂度
快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。
2.3.6 稳定性
快速排序是非稳定的
