1.快速排序
核心思路：
1.先从数列中取出一个数作为基准数。
2.分区过程，将比这个数大的放左边，比这个数小的放右边。
3.在对左右区间重复第二步，直到各区间只有一个数
不稳定的排序算法
public static int partition(int[] a,int low,int high){
int temp=a[low];
while(low<high){
while(low<high&&a[high]>=temp){
high--;
}
if(low<high){
a[low]=a[high];
low++;
}
while(low<high&&a[low]<temp){
low++;
}
if(low<high){
a[high]=a[low];
high--;
}
}
a[low]=temp;
return low;
}
public static void quickSort(int[] a,int low,int high){
if(low<high){
int i=partition(a,low,high);
quickSort(a,low,i);
quickSort(a,i+1,high);
}
}
2.冒泡排序
核心思路：
每一轮依次进行两两比较，将最大的数沉底
外圈：因为只剩下一个数时不用再比较，所以共须循环n-1次;
内圈：第一圈比较n个数，需要n-1次，最大数沉底，第二圈比较n-1个数，需要n-2次。在第i次排序中，比较次数n-i；总移动次数n(n-1)/2；
稳定的排序算法
public static void bubbleSort(int[] a){
boolean flag=true;
for(int i=0;i<a.length-1;i++){
if(flag==false)break;
flag=false;
for(int j=1;j<a.length-i;j++){
if(a[j]<a[j-1]){
int temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
flag=true;
}
}
}
}
3.直接插入排序
核心思路：每次将一条数据插入到有序序列中，将大于该数字的数据统一后移一位，形成新的有序序列。重复到全部有序。（顾名思义）
监视哨：无需重复判断数组下标是否越界，将每个a[i]赋给a[0]，当比较到0个位置时自动成立退出循环
稳定的排序算法
public static void insertSort(int[] a){
int i,j;
for(i=1;i<a.length;i++){
if(a[i]<a[i-1]){
int temp=a[i];
for(j=i-1;j>=0&&a[j]>temp;j--)
a[j+1]=a[j];
a[j+1]=temp;
}
}
}
4.希尔排序
又称缩小增量排序。直接插入排序的优化，利用直接插入排序N较小时效率高与N基本有序时效率高的特点，将数据分组进行直接插入排序。
不稳定的排序算法
public static void shellSort(int[] a){
int step=a.length/2;
int i,j;
while(step>0){
for(i=step;i<a.length;i++){
int temp=a[i];
for(j=i-step;j>=0&&a[j]>temp;j-=step){
a[j+step]=a[j];
}
a[j+step]=temp;
}
step=step/2;
}
}
5.直接选择排序
思路：每一圈比较获得最小值的下标，并付给当前数组的第一位。
时间复杂度：外循环n-1次，内圈循环n-1-i次 O(n^2)
不稳定的排序算法
public static void selectSort(int[] a){
for(int i=0;i<a.length-1;i++){
int min=i;
for(int j=i+1;j<a.length;j++){
if(a[j]<a[min])
min=j;//找到最小值的下标
}
if(min!=i){
int temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
}
6.归并排序
利用分治法。先递归地分解数列，再合并有序数列
public static void mergeArray(int[] a,int first,int mid,int last,int[] temp){
int i=first,j=mid+1;
int m=mid,n=last;
int k=0;
while(i<=m&&j<=n){
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=m)
temp[k++]=a[i++];
while(j<=n)
temp[k++]=a[j++];
for(i=0;i<k;i++)
a[first+i]=temp[i];
}
public static void mergeSort(int[] a,int first,int last,int[] temp ){
if(first<last){
int mid=(first+last)/2;
mergeSort(a,first,mid,temp);//左边有序
mergeSort(a,mid+1,last,temp);//右边有序
mergeArray(a,first,mid,last,temp);//合并两个有序数列
}
}
7.堆排序
重在理解筛选法调整堆 通过它构造堆 和 调整堆
每次通过每次构造小顶堆获得最小值，依次获得有序序列
为无序序列创建堆的时候时堆完全二叉树从下往上筛选，最后一个非叶子节点编号[n/2]-1
时间复杂度最坏情况O(n*log2n) 不稳定的排序算法
//筛选法调整堆算法 将以LOW为根节点的子树调整成小顶堆
public static void sift(int[] a,int low,int high){
int i=low;
int j=2*i+1;
int temp=a[i];
while(j<high){
if(j<high-1&&a[j]>a[j+1])
j++;
if(temp>a[j]){//若父母结点值较大
a[i]=a[j];//孩子节点中较小值上移
i=j;
j=2*i+1;
}
else
j=high+1;//退出循环
}
a[i]=temp;
}
public static void heapSort(int[] a){
for(int i=a.length/2-1;i>=0;i--){
sift(a,i,a.length);
}
for(int i=a.length-1;i>0;i--){
int temp=a[0];
a[0]=a[i];
a[i]=temp;
sift(a,0,i);
}
}
笔记本上写完 又敲到电脑上花了不少时间，希望自己常看看，如果对你有用点个赞/留个言呗~
