算法（一）排序

一般算法题的解题场景思路：排序、递归分治、贪心、动态规划、回溯法、暴力模拟

排序：

1.冒泡排序：时间复杂度O（ $图片说明$ ）、空间复杂度O（1）、稳定排序
2.选择排序：时间复杂度O（ $图片说明$ ）、空间复杂度O（1）、稳定排序
3.插入排序：时间复杂度O（ $图片说明$ ）、空间复杂度O（1）、稳定排序
4.快速排序：时间复杂度O（nlogn）、空间复杂度O（1）、非稳定排序
5.堆排序：时间复杂度O（nlogn）、空间复杂度O（1）、非稳定排序
6.归并排序:时间复杂度O（nlogn）、空间复杂度O（n）、稳定排序
7.基数排序：时间复杂度O（n）、空间复杂度O（n）

一般应用场景：根据时间复杂度和空间复杂度、稳定排序分析出的。
a.对于大量数据排序，很显然使用O（nlogn）的快排、堆排、归并会更快。
b.对于部分有序的数据排序，很显然使用冒泡、插入、快排比较合适。
c.根据稳定性需要选择对应的排序算法。

1.冒泡排序：时间复杂度O（ $图片说明$ ）、空间复杂度O（1）、稳定排序

（1）思想：以从小到大为例，将第i个元素与第i+1个元素进行比较，将较大元素放在i+1位上，之后比较i+1与i+2直到结束，每趟循环确定出了最大的元素，下一趟循环比较的范围缩小。
（2）实现：

   void sort(int[] arr){
        for(int i=0;i<arr.length;i++){
            boolean isSwaped=false;//该趟循环中是否交换
            //每趟循环从0下标开始，比较j与j+1元素，每趟确定一个最大元素，范围缩小
            for(int j=0;j<arr.length-i-1;j++){
                //从小到大：将大元素排在后
                if(arr[j]>arr[j+1]){
                    swap(arr,j+1,j);
                    isSwaped=true;
                }
                //优化：如果某一趟循环不产生任何交换，则表明已经有序
                if(!isSwaped){
                    return;
                }
            }
        }
    }
   void swap(int[] arr,int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }

2.选择排序：时间复杂度O（ $图片说明$ ）、空间复杂度O（1）、稳定排序

（1）思想：以从小到大为例，第i个元素是第i小，前面i-1个元素已经有序，那么每趟循环从后面元素中选择出最小的元素，放在第i个元素上，每趟循环确定一个最小元素。
（2）实现：

    void sort(int[] arr){
        for(int i=0;i<arr.length;i++){
            int temp=i;//该趟循环中最小元素下标
            //从第i+1开始找最小元素
            for(int j=i+1;j<arr.length;j++){
                if(arr[temp]>arr[j]){
                    temp=j;
                }
            }
            swap(arr,i,temp);//交换元素，将第i小元素放在第i位
        }
    }
   void swap(int[] arr,int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }

3.插入排序：时间复杂度O（ $图片说明$ ）、空间复杂度O（1）、稳定排序

（1）思想：以从小到大为例，第一个元素默认有序，i从1开始，将第i个元素往前插入，如果前一个元素大，将前一个元素后移，如果前一个元素小，则将第i个元素插入该位置结束。
（2）实现：

    void sort(int[] arr){
        //当前需要插入的元素是第i个
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];//临时保存第i个元素
            int j=i-1;
            while(j>=0&&arr[j]>temp){
                arr[j+1]=arr[j];//第j位元素后移
                j--;
            }
            arr[j+1]=temp;//插入第i个元素
        }
    }

4.快速排序：时间复杂度O（nlogn）、空间复杂度O（1）、非稳定排序

（1）思想：以从小到大为例，每趟循环以当前数组最左元素为中枢元素，i从前开始找比中枢元素大的第一个元素，j从后开始找比中枢元素小的第一个元素，如果i<j则交换该两个元素，继续寻找，直到i>=j交换完毕，此时，i元素是该中枢元素的正确位置，将中枢元素与该元素交换，该位置之前的元素比中枢元素都小，该位置之后的元素比中枢元素都大，然后从中枢元素正确位置为界，将数组分成两部分，继续快速排序。
（2）实现：

    void quickSort(int[] arr,int left,int right){
        if(left<right){
            int mid=fun(arr,left,right);//确定中枢元素的正确位置
            quickSort(arr,left,mid-1);
            quickSort(arr,mid+1,right);
        }
    }
    int fun(int[] arr,int left,int right){
        int temp=arr[left];//保存中枢元素
        int i=left+1,j=right;
        while(true){
            //往后找第一个比temp大的元素
            while(i<=j&&arr[i]<=temp){
                i++;
            }
            //往前找第一个比temp小的元素
            while(i<=j&&arr[j]>=temp){
                j--;
            }
            if(i>=j){
                break;
            }
            swap(arr,i,j);
        }
        //中枢元素归位，返回中枢元素正确位置
        arr[left]=arr[j];
        arr[j]=temp;
        return j;
    }
    void swap(int[] arr,int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }

5.堆排序：时间复杂度O（nlogn）、空间复杂度O（1）、非稳定排序

（1）思想：以从小到大为例，将第n/2-1~0个元素循环下沉操作确定一个大顶堆，然后将循环将第0个元素与最后一个元素交换，将最大的元素放在堆末，下次交换的元素范围减1，对堆顶元素重新下沉，再重新交换。
（2）实现：

    void sort(int[] arr){
        int n=arr.length;
        //从中间n/2-1开始往前进行下沉操作
        for(int i = n/2-1;i>=0;i--){
            downAdjust(arr,i,n);
        }
        //从最后一个元素开始确定当前的最大元素，交换后重新下沉
        for(int i=arr.length-1;i>0;i--){
            swap(arr,0,i);
            downAdjust(arr,0,i);
        }
    }
    void downAdjust(int[] arr,int k,int end){
        int temp=arr[k];//保存下沉元素
        int child=2*k+1;//确定左孩子元素位置
        while(child<end){
            //如果右孩子存在且右孩子更大，则如果交换应该交换右孩子
            if(child+1<end&&arr[child+1]>arr[child]){
                child++;
            }
            //如果父元素小于子元素，则将子元素上升，否则终止
            if(temp<arr[child]){
                arr[k]=arr[child];//大元素上升，替换即可，交换无意义
                k=child;//接下来对该元素的子元素的子元素进行下沉
                child=2*k+1;
            }else{
                break;
            }
        }
        //将元素放置在对应位置
        arr[k]=temp;
    }
    void swap(int[] arr,int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }

6.归并排序:时间复杂度O（nlogn）、空间复杂度O（n）、稳定排序

（1）思想：将数组分成两部分，将两部分分别进行归并排序，在进行合并，合并过程，要将两个数组的元素进行比较，需要用临时数组将合并的元素存储起来，然后在将临时数组放回原数组完成该部分排序。

    void sort(int[] arr) {
        mergeSort(arr,0,arr.length-1);
    }
    void mergeSort(int[] arr,int left,int right){
        if(left<right){
            int mid=(left+right)/2;//分数组
            mergeSort(arr,left,mid);
            mergeSort(arr,mid+1,right);
            merge(arr,left,mid,right);//合并
        }
    }
    void merge(int[] arr,int left,int mid,int right){
        int[] temp=new int[right-left+1];//临时数组
        int i=left,j=mid+1;//两部分数组的下标指针
        int k=0;//临时数组的下标指针
        while(i<=mid&&j<=right){
            //放较小元素
            if(arr[i]<=arr[j]){
                temp[k++]=arr[i++];
            }else{
                temp[k++]=arr[j++];
            }
        }
        //如果某个数组没有元素了，另一个有元素，则无法用比较进行放置
        while(i<=mid){
            temp[k++]=arr[i++];
        }
        while(j<=right){
            temp[k++]=arr[j++];
        }
        //将临时数组元素放回去
        for(int m=0;m<k;m++){
            arr[left+m]=temp[m];
        }
    }

7.基数排序：时间复杂度O（n）、空间复杂度O（n）

（1）思想：如果一个数组内的元素大小范围在0~n之内，则建立一个大小为n的数组，对原数组进行遍历计数，在遍历新数组，将计数的值放回到原数组中。
（2）实现：

    void sort(int[] arr,int n) {
        int[] temp=new int[n+1];//临时数组
        for(int i=0;i<arr.length;i++){
            temp[arr[i]]++;//统计为arr[i]的个数
        }
        int j=0;
        for(int i=0;i<temp.length;i++){
            //遍历i出现的次数放置元素
            while(temp[i]!=0) {
                arr[j++]=i;
                temp[i]--;
            }
        }

    }