常用排序算法

######1、数组排序的方法：
* Arrays.sort(数组); 
######String转int：
* int a = Integer.parseOf(字符串);
######2、定义integer类型：
Integer yk = new Integer(整形数字);
######3、返回两个值中为真的一个值：return a || b；
######4、对树的操作一般都是通过递归调用完成
######5、用两个栈来实现一个队列:
栈的操作：push（想栈中加入数据） pop（取出栈中元素） 对栈的操作会让栈的size自动改变（栈的size属性）
######6、创建ArrayList：
ArrayList<Integer> yk = new ArrayList<>();

7、字符串的常用操作：

• Char[] c = 字符串.toCharArray() ; //将一个字符串变为字符数组
• 字符串的长度：字符串.length
• 连接字符串：string1.concat(string2);
• 比较两个字符串：str1.compareTo( str2 )
• 返回字符在字符串中的位置：indexOf(int ch)
• 判断是否包含另一个字符串：contains(字符串)
• 返回一个子字符串：String substring(int beginIndex, int endIndex)

9、反转数字：

• 使用toString方法将数组转化为字符串，再将其作为可变字符串（StringBuilder sb1 = new StringBuilder("字符串");），然后使用可变字符串的reverse()输出反转后的字符串。

定义数组：

• char[] a = new char[5];
• 先说明数组保存的数据类型，数组名，一定要初始化数组：向数组中加东西或者指明数组长度。
• java中字符用单引号，字符串用双引号： char[] a = new char[]{'a','b'};

image.png
image.png

11、自定义函数实现反转链表：

//   输入一个链表头指针，返回反转后的链表投指针
private ListNode reverse(ListNode head){
        ListNode current = head;
        ListNode previous = null;
        while(current != null){
            ListNode temp  = current.next;
            current.next = previous;
            previous = current;
            current = temp;
        }
        return previous;
    }

13、常用算法总结：

• 冒泡排序：每次对数组进行遍历，找到本次遍历最小的元素，置为当前遍历的第一位；下一次遍历从当前最小位的下一位开始遍历

• 选择排序：每次遍历找到最小的一个数，放到当前遍历的第一个位置；下一次遍历从当前的交换过后的最小的数的下一个位置开始

• 插入排序：从当前的第一个数据的位置开始，判断第二个数：如大于第一个数，位置不变（放到第一个数的后面），如果小于第一个数，则当道第一个数的前面（交换位置）；再判断第三个数与前两个数 的关系，并进行相应的位置变换

• 希尔排序：确定一个间隔值i（大于1），将第一个数与第（i + 1）个数进行比较，当第一个数大于（i + 1）位置的数时，它们交换位置；小于时位置不变；再将第二个数与（i + 2）进行相应的比较；直到（i + n）等于最后一个数时，本轮比较结束。i - 1 之后进行下一轮比较。当i = 1时，是最后一次比较

• 归并排序：将数组进行对等分割，直到分割为一个数组只有一个元素为止。然后将数组一的唯一一个元素与数组二的唯一一个元素进行比较，并进行相应的位置变换后将数组一和数组二进行合并得到一个大的数组一；原先的小数组三和小数组四进行一样的操作得到一个大数组二，然后将大数组一和大数组二进行比较、交换位置后合并；一直进行此循环直到最后合并得到整个数组排序结束。

• 快速排序：在数组中规定一个“中间值”，然后遍历数组,比“中间值”小的移到“中间值”的左边，比“中间值”大的移到“中间值”右边，否则位置不变；此时“中间值”将元素分为了左右两个数组。对这两个数组进行同样的操作：找中间值然后与中间值进行比较、交换位置；循环此操作知道中间值左右两边只剩下一个值为止

image.png

15、冒泡排序：

    public static void maopaoSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;

                    flag = false;
                }
            }
            if (flag) break;
        }
    }

16、快速排序：

确定一个中间值，比这个值大的数移到其右边，比这个值小的数移到其左边

//    在大while循环之前，将数组的第一个元素作为基准，进行排序；当while循环结束后，将
//    操作后i，j对应的中间值与基准值进行交换，然后递归实现
    public static void quickSort(int[] arr,int low,int high){
        if (low > high)return;
        int i = low;
        int j = high;
        //temp就是基准位
        int temp = arr[low];

        while (i<j) {
            //先看右边，依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                int t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }

方式二：
public void quicksort(int [] a,int left,int right){
  int low=left;
  int high=right;
  //下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！
  if(low>high)//作为判断是否截止条件
    return;
  int k=a[low];//额外空间k，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
  while(low<high){//这一轮要求把左侧小于a[low],右侧大于a[low]。  
    while(low<high&&a[high]>=k){//右侧找到第一个小于k的停止
      high--;
    }
    //这样就找到第一个比它小的了
    a[low]=a[high];//放到low位置
    while(low<high&&a[low]<=k) {//在low往右找到第一个大于k的，放到右侧a[high]位置
      low++;
    }
    a[high]=a[low];   
  }
  a[low]=k;//赋值然后左右递归分治求之
  quicksort(a, left, low-1);
  quicksort(a, low+1, right);  
}

插入排序：

• 优化：在二次for循环之前，如果当前 i 对应的值大于前一个值，则不用进行下一个for循环

    static void Srot(int[] data){
        for (int i = 1; i < data.length; i++){
            if (data[i] < data[i - 1]){
                for (int j = i - 1; j >= 0; j--){
                    if (data[j] > data[j + 1]){
                        int temp = data[j];
                        data[j] = data[j + 1];
                        data[j + 1] = temp;
                    }else {
                        break;
                    }
                }
            }
        }
    }

19、选择排序：

    static void chooseSrot(int[] data){
        // 总共要经过 N-1 轮比较
        for (int i = 0; i < data.length - 1; i++) {
            int min = i;
            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }
            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = data[i];
                data[i] = data[min];
                data[min] = tmp;
            }
        }
    }

18、希尔排序：

• 希尔排序的排序间隔距离：distance = array.length;
• distance = distance / 2;

    public static void shellSort(int a[]){
        int d=a.length;
        int team=0;//临时变量
        for(;d>=1;d/=2)//共分成d组
            //到那个元素就看这个元素在的哪个组即可
            for(int i=d;i<a.length;i++){
                team=a[i];
                for(int j=i-d;j>=0;j-=d){
                    if(a[j]>team){
                        a[j+d]=a[j];
                        a[j]=team;
                    }else {
//                        所有当前一个数据大于后一个数据时，才用进行接下来的循环，但是当前一个数据和
//                        后一个数据已经有序时，直接break，可以使排序效果更好。
                        break;
                    }
                }
            }
    }

21、归并排序：

• 把待排序序列分为若干个子序列，将子序列整理为有序序列，然后再把子序列合并为整体有序序列。

• 归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取。

  
  image.png
• 移位运算和除运算的区别

    //    归并排序
    public static void mergeSort(int[] data) {
        sort(data, 0, data.length - 1);
    }

    public static void sort(int[] data, int left, int right) {
        if (left >= right)
            return;
        // 找出中间索引
        int center = (left + right) / 2;
        // 对左边数组进行递归
        sort(data, left, center);
        // 对右边数组进行递归
        sort(data, center + 1, right);
        // 合并
        merge(data, left, center, right);
    }

    public static void merge(int[] data, int left, int center, int right) {
        // 右数组第一个元素索引
        int s2 = center + 1;
        // 缓存左数组第一个元素的索引
        int s1 = left;

        // 临时数组（存放合并之后的数据）
        int[] tmpArr = new int[data.length];
        // third 记录临时数组的索引(下标）
        int third = left;

//        检验左右数组是否都有数据
        while (s1 <= center && s2 <= right) {
            // 从两个数组中取出最小的放入临时数组
            if (data[s1 ] <= data[s2]) {
                tmpArr[third++] = data[s1 ++];
            } else {
                tmpArr[third++] = data[s2++];
            }
        }
        // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
        while (s2 <= right) {
            tmpArr[third++] = data[s2++];
        }
        while (s1 <= center) {
            tmpArr[third++] = data[left ++];
        }
        // 将临时数组中的内容拷贝回原数组中
        // （原left-right范围的内容被复制回原数组）
        while (left<= right) {
            data[left] = tmpArr[s1++];
        }
    }

20、堆排序：

• 堆是一棵完全二叉树
• 二叉树中父节点及其对应的子节点：父节点：arr[i] 左孩子：arr[2i+1] 右孩子：arr[2i+2]
• 完全二叉树最后一个有子节点的父节点的位置：length / 2 （length：二叉树的长度）
• 完全二叉树每一层最多有2的（层级 / 2）次方个节点
• 堆排序的思想：以一个父节点为基准，父节点是他和他的左右孩子中的最大数（如果不是就进行调整），从最后一个有子节点的父节点开始进行调整，然后对该父节点的左边一个节点进行同样的调整，当该层的节点都调整完毕，到这些节点的上一层从右往左继续进行调整（调整后还要看他的子节点和孙子节点是否还是有序的，否则进行调整）；直到根节点为止，此时根节点就是最大节点。然后将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端；再将剩下的n-1个元素继续进行排序。

//    堆排序
public static void sort(int []arr){
    //1.构建大顶堆（arr.length/2-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);//重新对堆进行调整
    }

}
//     参数i：当前需要调整的数据的索引位置；length：数组的长度
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }
 
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

22、桶排序：

• 桶排序是一种用空间换取时间的排序，桶排序重要的是它的思想，而不是具体实现，时间复杂度最好可能是线性O(n)，桶排序不是基于比较的排序，而是一种分配式的。

• 桶排序的思想为：将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。 当然桶排序选择的方案跟具体的数据有关系，桶排序是一个比较广泛的概念，计数排序是一种特殊的桶排序，基数排序也是建立在桶排序的基础上。在数据分布均匀且每个桶元素趋近一个时间复杂度能达到O(n)，但是如果数据范围较大且相对集中就不太适合使用桶排序。

  
  
• 针对上图的代码实现：

    public static void bucketStore(int[] arr){
//        桶的个数，视具体的分类规则而定（桶最多数 = 要排序的数组长度）
        List[] buckets=new ArrayList[arr.length];
//        初始化
        for(int i=0;i<buckets.length;i++){
            buckets[i]=new ArrayList<Integer>();
        }
        //将待排序序列放入对应桶中
        for(int i=0;i<arr.length;i++){
            int index=arr[i]/10;//对应的桶号
            buckets[index].add(arr[i]);
        }
        //每个桶内进行排序(使用系统自带快排)
        for(int i=0;i<buckets.length;i++){
            buckets[i].sort(null);
            //顺便打印输出排序后的序列
            for(int j=0;j<buckets[i].size();j++){
                System.out.print(buckets[i].get(j)+" ");
            }
        }
    }

22、计数排序：

• 计数排序是一种特殊的桶排序：找到最小值min，再找最大值max。然后创建这个区间大小的数组，从min的位置开始计数（数组每个值对应于要排序的数组中该数值出现的次数，这样就可以最大程度地压缩空间，提高空间的使用效率。

  
  image.png

public static void countSort(int a[]){
    int min=Integer.MAX_VALUE;int max=Integer.MIN_VALUE;
    //找到max和min
    for(int i=0;i<a.length;i++){
        if(a[i]<min)
            min=a[i];
        if(a[i]>max)
            max=a[i];
    }
    int count[]=new int[max-min+1];//对元素进行计数
    for(int i=0;i<a.length;i++){
        count[a[i]-min]++;
    }
    //排序取值
    int index=0;
    for(int i=0;i<count.length;i++){
        while (count[i]-->0) {
            a[index++]=i+min;//有min才是真正值
        }
    }
}

23、基数排序：

• 思想：将自身拆分成一个个组成的元素，每个元素分别顺序分配放入桶中、顺序收集，当从前往后或者从后往前每个位置都进行过这样顺序的分配、收集后，就获得了一个有序的数列。

  
  

//    基数排序：
static void radixSort(int[] arr){
    List<Integer>bucket[]=new ArrayList[10];
    for(int i=0;i<10;i++){
        bucket[i]=new ArrayList<Integer>();
    }
    //找到最大值
    int max=0;//假设都是正数
    for(int i=0;i<arr.length;i++){
        if(arr[i]>max)
            max=arr[i];
    }
    int divideNum=1;//1 10 100 100……用来求对应位的数字
    while (max>0) {//max 和num 控制
        for(int num:arr){
            bucket[(num/divideNum)%10].add(num);//分配 将对应位置的数字放到对应bucket中
        }
        divideNum*=10;
        max/=10;
        int idx=0;
        //收集 重新捡起数据
        for(List<Integer>list:bucket){
            for(int num:list){
                arr[idx++]=num;
            }
            list.clear();//收集完需要清空留下次继续使用
        }
    }
}