算法：排序算法
测试数组是：
int[] arr = new int[8000];
for (int i = 0; i < arr.length; i++) {
arr[i] = new Random().nextInt(8000);
}
排序的分类
- 内部排序：指将需要处理的所有数据都加载到内部存储器（内存）中进行排序
- 外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储（文件等）进行排序
- 常见的排序算法：
算法的时间复杂度
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
时间复杂度：
一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O( f(n) )，称O(f(n))是算法的渐进时间复杂度，简称时间复杂度。
常见时间复杂度：
对数阶：O(log2n)
线性对数阶：O(nlog2n)
冒泡排序（Bubble Sorting）
冒泡排序的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底的气泡一样逐渐向上冒。
优化：因为排序过程总，各元素不断接近自己的位置，如果一趟下来没有进行过交换，就说明序列有序，因此可以在排序过程总设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。
代码：
测试时间：135ms
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]){
flag = false;
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
进行循环，每一次都会将最大的数放到数组的末尾，如果一次循环中没有发生交换说明已经排好序了，直接break。
优化后时间：91ms
boolean flag = true;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]){
flag = false;
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if (flag){
break;
}else{
flag = true;
}
}
选择排序（select sorting）
选择排序也是内部排序发，是从欲排序的数据中，按照指定的规则选出某一元素，在依规定交换位置后达到排序的目的。
基本思想：第一次从arr[0] ~ arr[n-1]总选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，第n-1次从arr[n-2] ~ arr[n-1]中选取最小值与arr[n-2]交换，总共通过n-1次。
时间：39
int k, temp;
for (int i = 0; i < arr.length; i++) {
k = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[k] > arr[j]){
k = j;
}
}
if (k != i){
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
}
插入排序（insertion sorting）
插入式排序属于内部排序算法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，达到排序的目的。
算法思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码一次与有序表元素的排序码进行比较，将它插入有序表中的适当位置，使之成为新的有序表。
时间：27ms
int k,current;
for (int i = 1; i < arr.length; i++) {
k = i;
current = arr[i];
for (int j = i-1; j >= 0; j--) {
if (current < arr[j]){
arr[k] = arr[j];
k = j;
}else{
break;
}
}
arr[k] = current;
}
当前数与之前的数一一比较，如果小于arr[j]向后退一步，k占该位置，如果大于break，将当前数放入合适位置。
希尔排序（donald shell sortiong）
希尔排序也是一种****插入排序，他是简单插入排序改进之后的一个更有效的版本，也称缩小增量排序。
基本思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
int temp;
//分组
for (int group = arr.length / 2; group > 0; group /= 2) {
for (int i = group; i < arr.length; i++) {
//遍历各组的元素
for (int j = i - group; j >= 0; j -= group) {
if (arr[j] > arr[j + group]){
temp = arr[j];
arr[j] = arr[j+group];
arr[j+group] = temp;
}
}
}
}
优化算法：使用移动的方式
for (int group = arr.length / 2; group > 0; group /= 2) {
//从第group个元素开始,逐个对其所在的组进行直接插入排序
for (int i = group; i < arr.length; i++) {
int j = i;
int tp = arr[j];
if (arr[j] < arr[j-group]){
while (j-group >= 0 && tp <arr[j-group]){
//移动
arr[j] = arr[j-group];
j -= group;
}
}
//当退出 while 后，就给tp找到插入的位置
arr[j] = tp;
}
}
快速排序（quick sorting）
对冒泡排序的一种改进。
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后在按此方法对这两部分数据分别进行快速排序，整个过程可以递归进行。
解法一：
private static void quickSort(int[] arr, int i, int j) {
if (i == j){
return;
}
int limit = arr[j];
int m = i, n = j, temp;
for (int k = i; k <= n; k++) {
if (arr[k] < limit){
temp = arr[k];
arr[k] = arr[m];
arr[m++] = temp;
}else if (arr[k] > limit){
temp= arr[k];
arr[k--] = arr[n];
arr[n--] = temp;
}
}
if (m-1 >= i){
quickSort(arr,i,m-1);
}
if (j >= n+1){
quickSort(arr,n+1,j);
}
}
//优化
private static void quickSort(int[] arr, int i, int j) {
if (i >= j){
return;
}
int limit = arr[j];
int m = i, n = j, temp;
for (int k = i; k <= n; k++) {
if (arr[k] < limit){
temp = arr[k];
arr[k] = arr[m];
arr[m++] = temp;
}else if (arr[k] > limit){
temp= arr[k];
arr[k--] = arr[n];
arr[n--] = temp;
}
}
quickSort(arr,i,m-1);
quickSort(arr,n+1,j);
}
解法二：
private static void quickSort1(int[] arr, int low, int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i<j) {
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort1(arr, low, j-1);
//递归调用右半数组
quickSort1(arr, j+1, high);
}
时间：3ms
归并排序（merge sorting）
该算法采用经典的分治（divide and conquer）策略。
分治法将问题分（divide）成一些小的问题然后进行递归求解，而治（conquer）的阶段则将分的阶段得到的各答案修补在一起，即分而治之。
对左右部分分别排序，排好序的左右部分组合到一起。
public static void mergeSort(int[] arr, int l, int r){
if (l == r){
return;
}
//分成左右去排序
int mid = (r - l) / 2 + l;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
//将排好序的左右部分 有序的组合到一起
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int mid, int r) {
int m = l,n = mid+1,index=0;
int[] a = new int[r - l + 1];
while (m <= mid && n <= r){
if (arr[m] > arr[n]){
a[index++] = arr[n++];
}else{
a[index++] = arr[m++];
}
}
while (m <= mid){
a[index++] = arr[m++];
}
while (n <= r){
a[index++] = arr[n++];
}
for (int i = r; i >= l; i--) {
arr[i] = a[--index];
}
}
时间：4ms
桶排序
一句话总结：划分多个范围相同的区间，每个子区间自排序，最后合并。
桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。
桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。
public static void bucketSort(int[] arr){
// 计算最大值与最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
// 计算桶的数量
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
// 将每个元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
// 对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
// 将桶中的元素赋值到原序列
int index = 0;
for(int i = 0; i < bucketArr.size(); i++){
for(int j = 0; j < bucketArr.get(i).size(); j++){
arr[index++] = bucketArr.get(i).get(j);
}
}
}
基数排序（radix sorting）
基数排序属于 分配式排序，又称桶子法，通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。
基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法。
基数排序是桶排序的扩展
基本思想：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，一次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
public static void radix(int[] arr){
int max = arr[0];
for (int i : arr) {
max = Math.max(max,i);
}
//取出最大数的位数，要进行几次桶排序
int maxLen = (max+"").length();
for (int i = 1,n=1; i <= maxLen; i++,n*=10) {
//使用10个桶
int[][] radix = new int[10][arr.length];
for (int value : arr) {
//从个位开始，取出每一位上的数
int index = value / n % 10;
//这里使用数组中的第一位作为记录数组中有数据的长度，其他位记录数据
radix[index][radix[index][0] + 1] = value;
radix[index][0]++;
}
//从桶中按照顺序取出来，放回原数组，进行下一轮排序
int idx = 0;
for (int[] ints : radix) {
int len = ints[0];
for (int j = 1; j <= len; j++) {
arr[idx++] = ints[j];
}
}
}
}
基数排序是对传统桶排序的扩展，速度很快。
堆排序（heap sorting）
堆的结构：
1，堆结构就是用数组实现的完全二叉树结构
2，完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3，完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4，堆结构的heapInsert与heapify操作
5，堆结构的增大和减少
6，优先级队列结构，就是堆结构
特性：
第n个元素的左子节点为 2 * n + 1 第n个元素的右子节点为 2 * n + 2 第n个元素的父节点为（n-1）/ 2
堆排序的步骤：
1，先让整个数组都变成大根堆结构，建立堆的过程:
1)从上到下的方法，时间复杂度为O(N*logN)2)从下到上的方法，时间复杂度为O(N)2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN)
3，堆的大小减小成0之后，排序完成
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//首先将数组成为一个大根堆
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
swap(arr, 0, --size);
//依次将堆顶元素放到最后，保证堆顶元素为未排序的部分的最大值
while (size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) /2);
index = (index - 1)/2 ;
}
}
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
总结
稳定和不稳定指的是：如果 a= b, a在b之前 排序之后a还是在b之前，那么就是稳定的，否则不稳定。
k：是“桶”的个数。
In-place 不占用额外内存，Out-place：占用额外内存。