图解算法--排序算法

文章来源地址https://uudwc.com/A/8pORY

目录

1.冒泡排序算法

2.选择排序算法

3.插入排序算法

4.希尔排序算法

5.归并排序算法

6.快速排序算法

1.冒泡排序算法

原理讲解：

1. 从待排序的数组中的第一个元素开始，依次比较当前元素和它相邻的下一个元素的大小。
2. 如果当前元素大于相邻元素，则交换这两个元素的位置，将较大的元素向后冒泡。
3. 继续比较相邻元素，重复以上步骤，直到遍历完整个数组。
4. 一轮遍历完成后，最大的元素将会排在最后面。
5. 重复执行上述步骤，每次遍历都将会使待排序的元素中最大的元素冒泡到正确的位置，直到所有元素都有序排列。

 传统的冒泡排序算法

package Sort.Bubble;

import java.util.Arrays;

public class javaDemo {
    public static void main(String[] args) {
        int nums[] = new int[]{1,4,36,7,42,2,12,5,2};
        int temp;
//        冒泡算法
        for (int i=0;i< nums.length-1;i++){
            for (int j=0;j< nums.length-i-1;j++){
                if (nums[j]>nums[j+1]){
                    temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(nums));
    }
}

传统的排序算法有个缺点，那就是不管数据是否已经完成排序都会固定执行n(n-1)/2次，而如果加入岗哨的概念进行改造冒泡排序算法就可以提高程序的执行效率

传统冒泡执行已经快要排序好的数组结果如下：

可以看到在第二轮时候就已经排序好了，但是还是不断进行遍历，所以加入一个岗哨（flag）判断功能，当第三轮时候，如果没有元素进行交换后直接退出排序 。

改进型冒泡排序法

package Sort.Bubble;

import java.util.Arrays;

public class Sentry {
    public static void main(String[] args) {
        int num[] = new int[]{1,4,5,2,7,8,9};
        int flag;
        int temp;
        for (int i= num.length-1;i>0;i--){
            flag = 0;
//            如果发生了交换则不跳出
            for (int j=0;j<i-1;j++){
                if (num[j]>num[j+1]){
                 temp = num[j];
                 num[j] = num[j+1];
                 num[j+1] = temp;
                 flag ++;
                }
            }
//            如果从头遍历结束都没有交换则直接退出
            if (flag == 0){
                break;
            }
            System.out.println("第"+(num.length-i)+"轮排序结果为"+ Arrays.toString(num));
        }
    }
}

 算法分析：

• 冒泡排序算法在最坏的情况下时间复杂度是O(n^2)
• 在最好的情况下时间复杂度是O(n)

2.选择排序算法

原理讲解： 

1. 遍历待排序的数组，将第一个元素作为当前最小值。
2. 从当前位置之后的元素中找到最小的元素，并记录其位置。
3. 如果找到了比当前最小值更小的元素，则将该元素的位置更新为当前最小值的位置。
4. 遍历完整个数组后，将最小值与当前位置的元素进行交换。
5. 继续从下一个位置开始重复以上步骤，直到遍历完整个数组。

案例代码

package Sort.Chose.chose;

import java.util.Arrays;

public class javaDemo {
    public static void main(String[] args) {
        int nums[] = new int[]{1,2,4,2,3,51,12,6,2};
        int min;
        int index;
        int temp;
        for (int i=0;i< nums.length-1;i++){
//            每一轮初始化最小值与最小值下角标
            min = nums[i];
            index = i;
            for (int j=i+1;j< nums.length;j++){
                if (min>nums[j]){
                    min = nums[j];
                    index = j;
                }
            }
             temp = nums[i];
            nums[i] = min;
            nums[index] = temp;
        }
        System.out.println(Arrays.toString(nums));
    }
}

 算法分析：

• 冒泡排序算法无论在最坏还是最好的情况下时间复杂度都是O(n^2)

3.插入排序算法

 原理讲解：

1. 将数组分为已排序和未排序两部分。一开始，将第一个元素视为已排序部分，其余元素视为未排序部分。
2. 从未排序部分选择第一个元素，依次与已排序部分的元素比较。
3. 如果选取的元素小于已排序部分的某个元素，则将该元素插入到正确的位置，同时将已排序部分中的元素向后移动一位。
4. 重复上述步骤，将未排序部分的每个元素逐个插入到已排序部分的正确位置。
5. 当所有元素都插入完成，即未排序部分为空时，排序完成。

案例代码  

package Sort.InsertSort;

import java.util.Arrays;

public class javaDemo {
    public static void main(String[] args) {
        int nums[] = new int[]{4,1,5,2,6,7,2};
        int temp;
        for (int i=0;i< nums.length;i++){
            for (int j=0;j<i;j++){
                if (nums[i]<nums[j]){
                    temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                }
            }
            System.out.println("第"+(i+1)+"轮排序结果为"+ Arrays.toString(nums));
        }
    }
}

算法分析：

• 冒泡排序算法在最坏的情况下时间复杂度是O(n^2)
• 在最好的情况下时间复杂度是O(n)

4.希尔排序算法

  原理讲解：

1. 首先，选择一个增量 gap，通常将数组长度的一半作为初始增量。
2. 将数组按照增量进行分组，并对每个分组使用插入排序算法进行排序。
3. 逐渐缩小增量，重复以上步骤，直到增量为 1。
4. 最后使用增量为 1 的插入排序对整个数组进行最后一次排序

案例代码：

package Sort.Shell;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 8, 3, 6, 4};
        int n = arr.length;

        // 定义增量序列
        int[] increments = {5, 3, 1};
        System.out.println("原始数组顺序为"+Arrays.toString(arr));
        // 遍历增量序列
        for (int increment : increments) {

            // 对每个增量进行插入排序
            for (int i = increment; i < n; i++) {
                int temp = arr[i];
                int j = i;
                // 在当前增量下，对子序列进行插入排序
                while (j >= increment && arr[j - increment] > temp) {
                    arr[j] = arr[j - increment];
                    j -= increment;
                }
                arr[j] = temp;
                System.out.println("当前增量为"+increment+"，当前数组为："+Arrays.toString(arr));
            }

        }
    }
}

算法分析：

• 希尔排序算法无论在最坏还是最好的情况下时间复杂度都是O(n^3/2)
• 空间最优解

5.归并排序算法

   原理讲解：

1. 将待排序的数组递归地分成两个子数组，直到每个子数组只有一个元素。
2. 对每个子数组进行合并操作，将两个有序的子数组合并成一个有序的数组。
3. 重复以上步骤，直到所有的子数组都被合并成一个完整的有序数组。

案例代码：

package Sort.MergeSort;

import java.util.Arrays;

public class mergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, temp); // 递归排序左半部分
            mergeSort(arr, mid + 1, right, temp); // 递归排序右半部分
            merge(arr, left, mid, right, temp); // 合并左右两个有序数组
        }
        System.out.println("当前顺序为"+Arrays.toString(arr));
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 左半部分起始索引
        int j = mid + 1; // 右半部分起始索引
        int k = 0; // 临时数组索引

        // 将左右两个有序数组按顺序合并到temp数组中
        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 (i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
    }
    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 8, 3, 6, 4};
        System.out.println("原始数组："+ Arrays.toString(arr));
        mergeSort(arr);
    }
}

算法分析：

• 归并排序算法无论在最坏还是最好的情况下时间复杂度都是O(nlogn)

6.快速排序算法

   原理讲解：

1. 选择一个基准元素（通常是数组的第一个或最后一个元素）作为参考点。
2. 将待排序的数组分成两个子数组，其中一个子数组中的元素小于等于基准元素，另一个子数组中的元素大于基准元素。
3. 对这两个子数组分别重复上述步骤，递归地进行快速排序。
4. 当子数组的长度为 1 或 0 时，递归终止。
5. 将排序好的子数组合并起来，即可得到完整的有序数组。

案例代码：

package Sort.Quick;

import java.util.Arrays;

public class QuickSort {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high); // 将数组划分为两部分，返回中轴元素的索引
            quickSort(arr, low, pivotIndex - 1); // 递归排序左半部分
            quickSort(arr, pivotIndex + 1, high); // 递归排序右半部分
        }
        System.out.println("当前数组为"+Arrays.toString(arr));
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low]; // 选择第一个元素作为中轴元素
        int left = low;
        int right = high;

        while (left < right) {
            // 从右向左找第一个小于等于中轴元素的位置
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            if (left < right) {
                arr[left] = arr[right];
                left++;
            }

            // 从左向右找第一个大于中轴元素的位置
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            if (left < right) {
                arr[right] = arr[left];
                right--;
            }
        }

        arr[left] = pivot; // 将中轴元素放置到最终位置
        return left; // 返回中轴元素的索引
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 8, 3, 6, 4};

        System.out.printf("原始数组：");
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
    }
}

 算法分析：

• 快速排序算法在最坏的情况下时间复杂度是O(nlog2n)
• 在最好的情况下时间复杂度是O(n)
• 公认最好的排序算法