几种基础常用的排序算法

桃扇骨 2023-10-01 10:49 12阅读 0赞

#### 冒泡算法 ####

每次遍历进行i与i+1的值进行比较，把大的值都往数组后面丢，保证了数组末尾的元素为最大。

public static int[] test1(int[] arr) {
        int temp;
        for(int i=arr.length-1;i>0;i--) {
            for(int j=0;j<i;j++) {
                // 前者如果小于后者，就调换
                if (arr[j] > arr[j+1]) {
                    temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(change(arr));
        return arr;
    }

#### 选择算法 ####

对于冒泡是同个理念，不过减少了交换的次数。从左往右遍历，基于左边界的值进行比较，找到最小的元素进行替换，保证左边界的值是最小的。

public static void test2(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i+1; j < arr.length; j++) {
                // 参照物 > 目标，交换
                if(arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(change(arr));
    }

#### 插入算法 ####

从左往右，每次都以i+1为右边界，然后i+1的元素需要插入已经排好序的\[0,i\]的数组里，从后面一直比较到前面，遍历从i到0，只要有元素大于i+1那个元素就交换，最后插入成功后\[0,i+1\]就是排好序的数组了。

public static void test3(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i+1; j > 0; j--) {
                // 前者 > 后者，交换;
                if(arr[j-1] > arr[j]) {
                    temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(change(arr));
    }

#### 希尔排序 ####

缩小增量排序，每次都以rightStart=k为右边界的开始遍历，然后以比较0+k与k+k的方式遍历数组，前者大于后者就替换，直到k=0

public static void test4(int[] arr) {
        int temp;
        int k = arr.length/2;
        while (k != 0) {
            for (int rightStart = k; rightStart < arr.length; rightStart++) {
                int left = rightStart - k;
                int right = rightStart;
                // 每次都是左右俩边对比
                while (right < arr.length) {
                    if(arr[left] > arr[right]) {
                        temp = arr[left];
                        arr[left] = arr[right];
                        arr[right] = temp;
                    }
                    left += k;
                    right += k;
                }
            }
            k /= 2;
        }
        System.out.println(change(arr));
    }

#### 归并算法 ####

把大数组拆分成小数组不断进行比较排序得到最终结果。比如\{1,2,3,4\} => \{1,2\},\{3.4\} => \{1\}, \{2\},\{3\},\{4\}。  
每次比较都需要新建一个临时一样大小的数组用来转比较结果。

public static void test51(int[] arr) {
        test52(arr, 0, arr.length - 1);
        System.out.println(change(arr));
    }
    // 归并2
    public static void test52(int[] arr, int left, int right) {
        if(left == right) {
            return;
        }
        int mid = (right + left) / 2;
        test52(arr, left, mid);
        test52(arr, mid + 1, right);
        test53(arr, left, mid, right);
    }
    
    // 归并3
    public static void test53(int[] arr, int left, int mid, int right) {
        // 比较2个数组的元素大小，设置到left 到 right里
        int leftIndex = left;
        int rightIndex = mid + 1;
        // 插入的临时排好序的数组;
        int[] tempArr = new int[right - left + 1];
        int tempIndex = 0;
        // 左边的界限为 left ---- mid，右边为 mid + 1  ----  right
        while(leftIndex <= mid && rightIndex <= right) {
            // 谁小，就设置谁
            if(arr[leftIndex] < arr[rightIndex]) {
                tempArr[tempIndex++] = arr[leftIndex++];
            } else {
                tempArr[tempIndex++] = arr[rightIndex++];
            }
        }
    
        // 遍历完，肯定只有一边的数组剩余，没加到临时数组里，加上
        while (leftIndex <= mid) {
            tempArr[tempIndex++] = arr[leftIndex++];
        }
        while (rightIndex <= right) {
            tempArr[tempIndex++] = arr[rightIndex++];
        }
        // 最后遍历设置到原数组里
        tempIndex = 0;
        for (int i = left;i<=right;i++) {
            arr[i] = tempArr[tempIndex++];
        }
    }

#### 快速排序 ####

思想跟归并是差不多的，都是分治。快排都会以左边界的元素为参照物，然后把比它小的往左边丢，大的就往右边丢。

// 快排1
    public static void test61(int[] arr) {
        test62(arr, 0, arr.length - 1);
        System.out.println(change(arr));
    }
    
    // 快排2
    public static void test62(int[] arr,int left, int right) {
       if(left >= right) {
           return;
       }
       // 参考物
       int referenceIndex = left;
       int reference = arr[left];
    
       // 结束点
       int endIndex = right;
    
       int temp;
       int tempIndex = left;
       while (left < right) {
    
           // 右边边 > reference, 右边++
           while (left < right && arr[right] >= reference) {
               right--;
           }
    
           // 左边 < reference, 左边++
           while (left < right && arr[left] <= reference) {
               left++;
           }
    
           // 左边 > reference , 右边 < reference,就交换
           if(arr[left] > reference && arr[right] < reference) {
               temp = arr[left];
               arr[left] = arr[right];
               arr[right] = temp;
           }
           // 找到了中间点
           if(left == right) {
               tempIndex = left;
           }
       }
       // 交换参照物到指定位置，实现左边 < tempIndex < 右边
       temp = arr[referenceIndex];
       arr[referenceIndex] = arr[tempIndex];
       arr[tempIndex] = temp;
    
       // 往左边跟右边继续
       test62(arr, referenceIndex, tempIndex);
       test62(arr, tempIndex+1, endIndex);
    
    }