基础算法-排序
冒泡排序
从左到右，把大的数字交换到右边，第一遍循环后 最大的数交换到了最右边，第二遍循环把第二大的数交换到了倒数第二个位置。
第 k 此循环把第 k 大的数字交换到 倒数第 k 的位置。
k-1 此循环后，数组有序
public class BubbleSort {
public static void bubbleSort(int a[],int n){
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}
public static void main(String[]args){
int []a=new int[100];
SortUtil.randomArray(a);
SortUtil.print(a);
bubbleSort(a,100);
SortUtil.print(a);
}
}
直接选择排序
数组划分为左右两个区域，有序区和无序区，每次从无序区找到最小的那个元素的位置，然后把它放到有序区的最后面，这样第一次遍历将最小的放到了第一个位置，第二次遍历将剩余元素的最小的放到第二个位置，这样最后就按照升序把元素全部放到了有序区。
public class SelectSort {
public static void selectSort(int a[],int n){
for(int i=0;i<n-1;i++){
int k=i;
for(int j=i+1;j<n;j++)
if(a[j]<a[k])
k=j;
if(k!=i){
int t=a[k];
a[k]=a[i];
a[i]=t;
}
}
}
public static void main(String[]args){
int a[]=new int[100];
SortUtil.randomArray(a);
SortUtil.print(a);
selectSort(a,100);
SortUtil.print(a);
}
}
直接插入排序
直接插入排序就跟整理扑克牌一样，每次把一张新的牌插入到已经排好序的牌的合适的位置中。
数组中排序的时候要将之前位置上的数字全部右移动一个位置，空出来的位置再来放要插入的数字。
可以一次性全部右移动一个位置，也可以这样，因为要插入的数字在已经排序的区间的右边
如果要插入的数字左边的数字比要插入的数字大，那么就跟左边的数字交换位置，这样如果到了左边位置的数字小于等于它的时候
说明它已经到了正确的位置了。
public class InsertSort {
public static void insertSort(int a[],int n){
for(int i=1;i<n;i++){
for(int j=i-1;j>=0&&a[j]>a[j+1];j--){
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
public static void main(String[]args){
int a[]=new int[100];
SortUtil.randomArray(a);
SortUtil.print(a);
insertSort(a,100);
SortUtil.print(a);
}
}
希尔排序
希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
public class ShellSort {
public static void shellSort(int a[],int n){
for(int g=n/2;g>0;g/=2){
for(int i=g;i<n;i++){
for (int j=i-g;j>=0&&a[j]>a[j+g];j-=g){
int t=a[j];
a[j]=a[j+g];
a[j+g]=t;
}
}
}
}
public static void main(String[]args){
int a[]=new int[100];
SortUtil.randomArray(a);
SortUtil.print(a);
shellSort(a,100);
SortUtil.print(a);
}
}
堆排序
堆:任意节点的值大于（小于)左右子节点的值，子节点也为堆。
如果对于存储在数组里的堆的话, 节点下标为 j, 它左子节点下标为 2j+1, 右子节点下标为 2j+2;
堆排序（升序）:
调整堆：如果节点的左子节点与右子节点都已经是大根堆，调节该节点也为大根堆.
如果该节点的左右子节点的值都小于该节点，结束。（已经是大根堆）
选定一个最大的子节点 j，将当前根节点的值与最大子节点 p 的值交换，这样，a[p]>a[j],a[p]>a[j+1], 这里符合堆
但是将之前 a[p] 的值往下移动后，这个节点不一定是堆（但是它原来的左右节点已经是堆），因此继续调整 a[p] 为堆。
选择:
从 j=n*2-1 开始调整（从第二层最右边的节点开始），这样一层一层的调整，最后，最根节点的值为最大的值。
每次将最大的值与堆后面的值交换，然后减小堆的大小，重新调整最根节点为堆，重复这个步骤
public class HeapSort {
public static void adjust(int a[],int n,int p){
for(int j=2*p+1;j<n;j=2*p+1){
if(j+1<n&&a[j]<a[j+1])
j=j+1;//j 为大的子节点下标
if(a[j]<a[p])// 如果大的子节点比父节点小，结束（父节点已经为堆）
break;
int t=a[p];//根节点比子节点小，交换位置，导致新的子节点不为堆，继续调整子节点
a[p]=a[j];
a[j]=t;
p=j;//需要继续调整的子节点
}
}
public static void adjust2(int a[],int n,int p){
int t=a[p];//相比于上面，因为每次 t 都是保存最开始要调节的那个节点的值，只是不断往下移动位置
//可以省略步骤
for(int j=2*p+1;j<n;j=2*p+1){
if(j+1<n&&a[j]<a[j+1])
j++;
if(a[j]<t)
break;
a[p]=a[j];
p=j;
}
a[p]=t;
}
public static void heapSort(int a[],int n){
for(int i=n/2-1;i>=0;i--)
adjust(a,n,i);
for(int i=n-1;i>0;i--){
int t=a[0];
a[0]=a[i];
a[i]=t;
adjust2(a,i,0);
}
}
public static void main(String[]args){
int a[]=new int[100];
SortUtil.randomArray(a);
SortUtil.print(a);
heapSort(a,a.length);
SortUtil.print(a);
}
}
快速排序
选择一个基准值x,把比x小的全部放在左边，把大于等于x的值放在右边，然后把x放到这个边界.
这样,如果左边是升序的，那么因为x比左边的都大，左边区间加上x 的这个区间同样是升序的，如果此时右边也是升序的，
那么因为x的值小于等于右边的值，则整个数组是升序的
而每个区间的排序，可以递归调用快速排序完成，如果区间只有一个值就不用排序了。
public class QuickSort {
public static void quickSort(int a[],int l,int r){
if(l<r){//递归出口
int i=l,j=r,x=a[i];//选定第一个元素为基准
while (i<j){
while (i<j&&a[j]>=x)//第一个小于x的值
j--;
if(i<j)
a[i++]=a[j];//小于x的值全部放在左边 (i++好像也没有必要，
// 因为到下面的话,这个值肯定是小于x的，再下面的那个while 中自然会+1
while (i<j&&a[i]<x)//第一个大于等于x的值
i++;
if(i<j)
a[j--]=a[i];//大于等于x的值全部放在右边,(j--同样也没有什么必要)
}
a[i]=x;//正好停留的位置为左边小于x，右边大于等于x
quickSort(a,l,i-1);//递归快排左边
quickSort(a,i+1,r);//递归快排右边
}
}
public static void main(String[]args){
int a[]=new int[100];
SortUtil.randomArray(a);
SortUtil.print(a);
quickSort(a,0,a.length-1);
SortUtil.print(a);
}
}
归并排序
思想：如果需要排序的数组分为两个部分，左边是有序的，右边也是有序的（都是升序或者都是降序），那么将两个区间合并为有序的只需要o（n）的复杂度就可以完成。那么如果这两个区域不是有序的呢，可以递归的调用归并排序，直到区间的元素只有一个元素，那么这个区间就是有序的，回到上一层调用，左右两个区间已经有序的情况下，把它们合并在一起，那么这一层就有序了。直到回到了第一层，那么整个数组就有序了。
public class MergeSort {
// [l,m] 区间升序， [m+1,r] 区间升序 ，通过 tmp[] 将它们合并仍然有序
private static void merge(int a[],int l,int m,int r,int tmp[]){
int i=l,j=m+1,k=0;
while (i<=m&&j<=r){
if(a[i]<a[j])
tmp[k++]=a[i++];
else
tmp[k++]=a[j++];
}
while (i<=m)
tmp[k++]=a[i++];
while (j<=r)
tmp[k++]=a[j++];
for(i=0;i<k;i++)
a[l+i]=tmp[i];
}
private static void mergeSortInner(int a[],int l,int r,int tmp[]){
if(l<r){
int m=(l+r)/2;
mergeSortInner(a,l,m,tmp);//先递归排序，使得左边升序
mergeSortInner(a,m+1,r,tmp);//递归排序，使得右边升序
merge(a,l,m,r,tmp);//合并两个升序的区间为有序
}
}
//一次性创建临时数组，避免每次合并时新建新的临时数组
private static void mergeSort(int a[],int n){
int tmp[]=new int[n];
mergeSortInner(a,0,n-1,tmp);
}
public static void main(String[]args){
int a[]=new int[100];
SortUtil.randomArray(a);
SortUtil.print(a);
mergeSort(a,100);
SortUtil.print(a);
}
}
