image.png
1、冒泡算法
流程
前后两个元素进行比较，大的往后移
第一轮会将最大的元素移到最后面，第二轮会将第二大的元素移到倒数第二个，以此类推。
缺点
时间平均复杂度O(n^2)
优点
容易实现
public int[] bubbleSort(int[] a){
if(a == null || a.length == 1) return a;
int length = a.length;
for(int i = length - 1; i > 0; i --){
for(int j = 0; j < i; j++){
if(a[j] > a[j + 1])
swap(a, j , j + 1);
}
}
return a;
}
优化
1）针对已经排好序的数组，如果某一轮中，前后元素两两都没有交换，那么这个数组是排序好的，则可以退出循环，实现是设置一个flag，默认为false,当某一轮中元素有交换，则将flag设置为true,就不会跳出循环，下一轮开始flag又设置为false，以此类推。
public int[] bubbleSort(int[] a){
if(a == null || a.length == 1) return a;
int length = a.length;
for(int i = length - 1; i > 0; i --){
boolean flag = false;
for(int j = 0; j < i; j++){
if(a[j] > a[j + 1]){
swap(a, j , j + 1);
flag = true;
}
}
if(!flag) break;
}
return a;
}
2）
下一步只循环到最后面有交换位置的地方，没有那些没有交换位置说明已经后面排序好了。
public int[] bubbleSort(int[] a){
if(a == null || a.length == 1) return a;
int length = a.length;
int pos = 0;
for(int i = length - 1; i > 0; i = pos){
for(int j = 0; j < i; j++){
if(a[j] > a[j + 1]){
swap(a, j , j + 1);
pos = j;
}
}
}
return a;
}
2、选择排序
不稳定
举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了。
流程
循环数组元素，将数组元素与后面的元素相比较，定义一个最小值下标，找出最小值元素的下标，最后进行交换。
public int[] selectSort(int[] a){
if(a == null || a.length == 1) return a;
int length = a.length;
for(int i = 0; i < length; i++){
int tempIndex = i;
for(int j = i +1; j < length; j++){
if(a[j] < a[tempIndex])
tempIndex = j;
}
if(tempIndex != i)
swap(a, i, tempIndex);
}
return a;
}
3、插入排序
分析
时间平均复杂度: O(n^2) 最佳O(n) 最坏O(n^2)
流程
循环数组元素，为每一个元素查找从前面查找可以插入的位置。
public int[] insertSort(int[] a){
if(a == null || a.length == 1) return a;
int length = a.length;
for(int i = 1; i < length; i++){
for(int j = i ; j > 0&&a[j] < a[j - 1] ; j--){
swap(a, j , j - 1);
}
}
return a;
}
优化
解决排序时每一步交换，直接找到可以插入的位置，
前面的相应往后移位，最后在保存的位置保存那个元素
public int[] insertSort(int[] a){
if(a == null || a.length == 1) return a;
int length = a.length;
for(int i = 1; i < length; i++){
int e = a[i];
int j = 0;
for(j = i ; j > 0&&a[j] < a[j - 1] ; j--){
a[j] = a[j - 1];
}
a[j] = e;
}
return a;
}
4、希尔排序
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
public int[] insertSort(int[] a){
if(a == null || a.length == 1) return a;
int length = a.length;
int h = 0;
while(h < length){
h = h * 3 + 1;
}
while(h > 0){
for(int i = h; i < length; i++){
for(int j = i ; j > h &&a[j] < a[j - h] ; j-=h){
swap(a, j , j - h);
}
}
h = h/3 - 1;
}
return a;
}
5、归并排序
public int[] mergeSort(int[] a,int lo, int hi){
sort(a, 0 ,length - 1);
return a;
}
private void __mergeSort(int[] a,int lo, int hi){
if(lo >= hi) return;
int mid = (hi - lo)/2 + lo;
__mergeSort(a, lo ,mid);
__mergeSort(a, mid + 1, hi);
merge(a,lo,mid,hi);
}
private void merge(int[] a, int lo, int mid, int hi){
int i = lo, j = mid + 1;
for(int k = lo; k <= hi; k++){
aux[k] = a[k];
}
for(int k = lo; k <= hi; k++){
if(i > mid) a[k] = aux[j++];
if(j > hi) a[k] = aux[i++];
if(aux[i] > aux[j]) a[i] = aux[j++];
else a[j] = aux[i++];
}
}
6、快速排序
单路快排
缺点:
1、当一个数组近乎有序，一分为二的时候，几乎都是右边很大，左边很小，这样
会使得退化为O(n^2)。数据近乎反序类似。
解决办法: 从数组范围随机选择一个元素，与第一个元素交换位置
2、当一个数组极多元素，但取值范围很小[0,10],这样也会导致与情况1一分为二类似的情况，因为与第一个元素比较太多相同的。
解决办法:双路快排
public int[] quickSort(int[] a){
__quickSort(a, 0 , a.length-1);
}
private void __quickSort(int[] a,int lo,int hi){
if(lo >= hi) return;
int j = partition(a, lo ,hi);
__quickSort(a, lo, j - 1);
__qucikSort(a, j + 1, hi);
}
private int parition(int[] a, int lo, int hi){
// [lo+1,j) < v [j,hi] >= v
int v = a[lo];
int j = lo + 1;
for(int i = lo + 1; i <= hi ; i++){
if(a[i] < e){
swap(a, i, j);
j++;
}
}
swap(a,lo,j);
return j;
}
双路快排
public int[] quickSort(int[] a){
__quickSort(a, 0 , a.length-1);
}
private void __quickSort(int[] a,int lo,int hi){
if(lo >= hi) return;
int j = partition(a, lo ,hi);
__quickSort(a, lo, j - 1);
__qucikSort(a, j + 1, hi);
}
private int parition(int[] a, int lo, int hi){
int i = lo,j = hi + 1;
int e = a[i];
while(true){
while(i < hi && a[++i] > e); // 不会越界因为==hi就跳出循环
while(j > lo && a[--j] < e); // 不会越界因为==lo就跳出循环
if(i > j) break;
swap(a, i ,j);
}
swap(a, lo ,j);
return j;
}
三路快排
lt 代表小于v的最后一个元素，所以交换的时候是lt+1（==v）的元素与小于v的元素进行交换
gt 代表大于v的第一个元素，所以交换的时候是gt - 1（==v）的元素与大于v的元素进行交换
public int[] quickSort(int[] a){
__quickSort(a, 0 , a.length-1);
}
private void __quickSort(int[] a,int lo,int hi){
if(lo >= hi) return;
int v = a[lo];
int lt = lo;//[lo + 1, lt] < v
int gt = hi + 1; // [gt, hi] > v
int i = lo + 1; // [lt , i) == v
while(i < gt){
if(a[i] < v){
swap(a, lt + 1, i);
lt++, i++;
}if(a[i] > v){
swap(a, gt - 1, i);
gt--;
}else
i++;
}
swap(a, lt, lo);
__quickSort(a, lo, lt);
__qucikSort(a, gt, hi);
}
7、堆排序
public static void sort(int []arr){
//1.构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对堆进行调整
}
}
/**
* 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
* @param arr
* @param k
* @param length
*/
private static void adjustHeap(int []arr,int k,int length){
while(k * 2 + 1 < length){
int j = k * 2 + 1; // 获得左子节点
if(j + 1 < length&& arr[j+ 1] > arr[j]){ // 右子节点存在并且右子节点大于左子节点，则要比较的值就是右子节点
j = j + 1;
}
if(arr[k] >= arr[j]) // 右子节点还小于父节点的话，说明已经保持了堆定义，不用进行下沉。
break;
swap(arr, j , k);
k = j;
}
}
/**
* 交换元素
* @param arr
* @param a
* @param b
*/
private static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
最大堆
插入--上升，插入到数组尾
private void shitUp(int k){
while(k > 0 && arr[k] > arr[k/2]){ // 父节点为k/2，当父节点小于子节点，则交换
swap(arr, k , k/2);
k /= 2;
}
}
删除--下沉，取数组末尾的元素到第一个元素
private void shitDown(int k,int length){
while(k * 2 <= length){
int j = k * 2; // 获得左子节点
if(j + 1 <= length&& arr[j+ 1] > arr[j]){ // 右子节点存在并且右子节点大于左子节点，则要比较的值就是右子节点
j = j + 1;
}
if(arr[k] <= arr[j]) // 右子节点还小于父节点的话，说明已经保持了堆定义，不用进行下沉。
break;
swap(arr, j , k);
k = j;
}
}
