冒泡排序
时间复杂度O(n^2)
public static void bubbleSort(int[] arr){
int temp=0;
boolean flag=false;
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1])
{
flag=true;
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
if(!flag)
return;
else
flag=false;
}
}
选择排序
时间复杂度O(n^2)
public static void selectSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
int minIndex=i;
int min=arr[i];
for(int j=i+1;j<arr.length;j++){
if(min>arr[j]){
min=arr[j];
minIndex=j;
}
}
if(minIndex!=i){
arr[minIndex]=arr[i];
arr[i]=min;
}
}
}
冒泡排序与选择排序的区别
冒泡排序是将“最大值”不断移向最后，比如第一次遍历，将全部数的最大值移到最后一个位置，第二次遍历，将从开始到倒数第二个数中的最大值移到倒数第二个位置，以此类推。过程中可能存在多次交换
选择排序是首先将第一个数到最后中的最小值与第一个数交换，然后从第二个数开始，一直到最后，找出最小值，与第二个数交换，以此类推。在一次遍历中有且只交换一次
插入排序
时间复杂度O(n^2)
public static void insertSort(int[] arr){
for(int i=1;i<arr.length;i++){
int insertVal=arr[i];
int insertIndex=i-1;
while(insertIndex>=0&&insertVal<arr[insertIndex]){
arr[insertIndex+1]=arr[insertIndex];
insertIndex--;
}if(insertIndex+1!=i){
arr[insertIndex+1]=insertVal;
}
}
}
原理：
希尔排序
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序的时间复杂度比较模糊，它取决于增量，大概范围是O(n^(1.3-2))，但是可以肯定的是希尔排序比直接插入排序要更有效率
public static void shellSort(int[] arr){
int temp=0;
int count=0;
for(int gap=arr.length/2;gap>0;gap/=2){
for(int i=gap;i<arr.length;i++)
for(int j=i-gap;j>=0;j-=gap)
if(arr[j]>arr[j+gap]){
temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}
}
}
希尔排序的原理很好理解，但是代码需要思考一下：
for(int gap=arr.length/2;gap>0;gap/=2){
for(int i=gap;i<arr.length;i++)
for(int j=i-gap;j>=0;j-=gap)
if(arr[j]>arr[j+gap]){
temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}
}
关于这里，最外层循环是增量，中间层的 i 从gap开始，即从第一个分组的第二个元素开始，也就是说跳过所有分组的第一个元素，以便接下来进行判断，交换位置
最里层 j 从 i-gap开始，也就是从 i 所在分组的前一个元素开始判断，j 递减gap，一直到0，也就是将 arr[i]移到所在分组的排序后的位置
，也就是之前的插入排序
i 一直遍历到arr.length，从而将所有分组的所有元素（从第二个开始）都在所在分组进行了插入排序
最后随着gap折减到0，排序完成
快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
快速排序的平均时间复杂度是O(nlogn)，最坏情况是O(n^2)
public static void main(String[] args) {
int[] arr=new int[]{9,8,7,6,5,4,3,2,1,0};
quickSort(arr,0,arr.length-1);
for(int e:arr)
System.out.print(e);
}
public static void quickSort(int[] arr,int left,int right){
if(arr==null||arr.length==0)
return;
if(left>right)
return;
int key=arr[left];
int l=left;
int r=right;
int temp=0;
while(l!=r){
while(arr[r]>=key&&l<r)
r--;
while(arr[l]<=key&&l<r)
l++;
if(l<r){
temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
}
}
arr[left]=arr[r];
arr[l]=key;
quickSort(arr,left,l-1);
quickSort(arr,l+1,right);
}
归并排序
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer)策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
归并排序的时间复杂度是O(nlogn)
public class MergeSort {
public static void main(String[] args) {
int[] arr=new int[]{9,8,7,6,5,4,3,2,1,0};
int[] temp=new int[arr.length];
mergeSort(arr,0,arr.length-1,temp);
for(int e:arr)
System.out.print(e);
}
public static void mergeSort(int[]arr,int left,int right,int[]temp){
if(left<right){
int mid=(left+right)/2;
mergeSort(arr,left,mid,temp);
mergeSort(arr,mid+1,right,temp);
merge(arr,left,mid,right,temp);
}
}
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i=left;
int j=mid+1;
int t=0;
while(i<=mid&&j<=right){
if(arr[i]<=arr[j])
temp[t++]=arr[i++];
else
temp[t++]=arr[j++];
}
while(i<=mid)
temp[t++]=arr[i++];
while(j<=right)
temp[t++]=arr[j++];
t=0;
int tempLeft=left;
while(tempLeft<=right)
arr[tempLeft++]=temp[t++];
}
}
基数排序
基数排序(桶排序)介绍:
1)基数排序(radix sort)属于"分配式排序"(distribution sort)，又称"桶子法”(bucket sort)或bin sort、顾名思义，它是通过键值的各个位的值,将要排序的元素分配至某些“桶"中达到排序的作用
2)基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法，稳定性排序指:如一个数组原来为3,1,4,1排序后为1,1,3,4，红色的1仍然在前面。
3)基数排序(Radix Sort)是桶排序的扩展
4)基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字，然后按每个位数分别比较
5）基数排序法的时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数
基数排序基本思想
将所有待比较数值统一为同样的数位长度．数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
例如：将数组{53,3,542,748,14,214}使用基数排序,进行升序排序
public static void radixSort(int[] arr){
int max=arr[0];
for(int i=0;i<arr.length;i++){
max=max>arr[i]?max:arr[i];
}
int maxLength=(max+"").length();//数字最大位数
int[][] bucket=new int[10][arr.length];//十个桶子，每个深为arr.length
int[] bucketElementCounts=new int[10];//用于记录每个桶子里面存放了几个数据，便于取出
for(int i=0,n=1;i<maxLength;i++,n*=10){//次数为数字最大位数的循环
for(int j=0;j<arr.length;j++)//依次放入桶子
{
int digitOfElement=arr[j]/n%10;
bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
bucketElementCounts[digitOfElement]++;
}
int index=0;
for(int k=0;k<10;k++){//依次取出
if(bucketElementCounts[k]!=0){
for(int m=0;m<bucketElementCounts[k];m++)
arr[index++]=bucket[k][m];
}
bucketElementCounts[k]=0;//记得将桶子中存放个数清零
}
}
}
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，是一种选择排序，它的最坏，最好．平均时间复杂度均为O(nlogn)，它也是不稳定排序（不能保证相同的两个数的位置和原来一样)
堆是具有以下性质的完全二叉树(叶子节点只出现在最后一层或倒数第二层)∶
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
（注意:没有要求结点的左孩子的值和右孩子的值的大小关系）-
每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
一般升序采用大顶堆，降序用小顶堆
堆排序的基本思想是:
- 将待排序序列构造成一个大顶堆
- 此时，整个序列的最大值就是堆顶的根节点
- 将其与末尾元素进行交换,此时末尾就为最大值
- 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了
public static void heapSort(int[] arr){
int temp=0;
for(int i=arr.length/2-1;i>=0;i--)
adjustHeap(arr,i,arr.length);
for(int j=arr.length-1;j>0;j--){
temp=arr[j];
arr[j]=arr[0];
arr[0]=temp;
adjustHeap(arr,0,j);
}
}
/**
*
* @param arr 待调整数组
* @param i 非叶子节点在数组中的索引
* @param length 表示对多少个元素进行调整，是递减的
*/
public static void adjustHeap(int[] arr,int i,int length){
int temp=arr[i];
for(int k=i*2+1;k<length;k=k*2+1){
if(k+1<length&&arr[k]<arr[k+1])
k++;
if(arr[k]>temp)
{
arr[i]=arr[k];
arr[k]=temp;
i=k;
}else
break;
}
}
https://www.cnblogs.com/coding-996/p/12275710.html
https://www.cnblogs.com/chengxiao/p/6104371.html
