排序算法

2021/7/8 20:16:15

本文主要是介绍排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

内部排序算法

分类

  1. 插入排序
    • 直接插入排序
    • 折半插入排序
    • 希尔排序
  2. 交换排序
    • 冒泡排序
    • 快速排序
  3. 选择排序
    • 简单选择排序
    • 堆排序
  4. 归并排序
  5. 基数排序

直接插入排序

  1. 算法思想

    对于一组数据,只有一个数时,一定有序。因此只需要从第二个数开始确定它在有序序列中的位置,然后将其移到该位置

  2. 算法实现步骤

    /**
     * 直接插入排序(从小到大)
     * 从第二位开始,依次向前比较,如果遇到比它大的移动位置
     */
    public static void insertDirectly(int[] A) {
        int[] array = A;
        System.out.println("初始:");
        inputArray(array);
        int len = array.length;
        for (int i = 1; i < len; i++) {
    
            // 0 到 i - 1 这个序列一定是有序的,若 array[i] > array[i - 1] 此时的元素已经在它应在的位置上
            // 所以只需要考虑当前元素在有序序列中的位置
            for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
                array[j] = array[j] ^ array[j - 1];
                array[j - 1] = array[j] ^ array[j - 1];
                array[j] = array[j] ^ array[j - 1];
            }
        }
        System.out.println("直接插入排序:");
        
        inputArray(array);
    }
    

折半插入排序

  1. 算法思想

​ 基于直接插入排序,只是在确定插入位置时采用折半查找

  1. 实现

    /**
     * 折半插入排序
     * 跟直接插入相比只是在查找位置时,采用折半查找。
     */
    public static void halfInsert(int[] A) {
        int[] array = A;
        int len = array.length;
        for (int i = 1; i < len ; i++) {
            // 存放当前value的值
            int value = array[i];
            // 定义 low 和high 确定查找的范围
            int low = 0;
            int high = i - 1;
            int middle;
            // 折半查找
            while (low <= high) {
                middle = (low + high) / 2;
                if (array[middle] > value) {
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
    
            //移位
            for(int j = i - 1; j >= high + 1; j--){
                array[j + 1] = array[j];
            }
            array[high + 1] = value;
        }
    }
    

希尔排序(鸽一下下)

冒泡排序

  1. 算法思想

    每轮从 i = 0 开始,确定一个最大的数或者最小的数

  2. 实现

    /**
     * 冒泡排序 (从小到大)
     * 每一次都从 i = 0开始,与相邻的下一个元素开始比较,遇到比它小的交换位置,直到数组有序为止
     * 第一个for 循环控制一共需要比较几轮  len - 1
     * 第二个for 循环控制每次比较的次数
     */
    public static void bubble(int[] A) {
        int[] array = A;
        System.out.println("初始:");
        inputArray(array);
        int len = array.length;
    
        // 设置flag 当不发生交换时,证明数组已经有序,直接退出循环
    
        for (int i = 1; i < array.length; i++) {
            boolean flag = true;
            for (int j = 0; j < len - i; j ++) {
                if (array[j] > array[j + 1]) {
                    array[j] += array[j + 1];
                    array[j + 1] = array[j] - array[j + 1];
                    array[j] = array[j] - array[j + 1];
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        System.out.println("冒泡排序:");
        inputArray(array);
    }
    

快速排序

  1. 算法思想

    每次选择一个数作为基数(一般都选第一个数),将所有比这个数大的放在这个数的右边,比它小的放左边

    对新产生的两个序列分别按上诉方法再次拆分

  2. 对于 3 7 2 6 1 4 5 这个序列

  • 选择第一个数 3 作为基数, 用两个指针实现把比基数大的移到右边,比基础小的移到左边。

  • (1)要先动 high指针,5 > 3 不用移动,所以 high–, 此时 4 > 3 high – , 1 < 3
    就令 array[low] = array[high] (low 此时在 0 处)跳到2

  • (2)再动 low 指针,1 < 3 所以 low++, 7 >3 所以 令array[high] = array[low],返回1

  • 上诉过程就是 3 7 2 6 1 4 5 ——> 1 7 2 6 1 4 5 (low = 0, high = 4) ->

    1 7 2 6 7 4 5(low = 1 high = 4) -> 1 2 2 6 7 4 5 (low = 1, high = 2) ->1 2 2 6 7 4 5(low = 2, high = 2)

  • 最后令array[low] = base;

/**
 * 快速排序
 * 每次选择一个数作为基数(一般都选第一个数),将所有比这个数大的放在这个数的右边,比它小的放左边
 * 对新产生的两个序列分别按上诉方法再次拆分
 */
public static void quick(int[] array, int high, int low) {
    if (low < high) {
        int base = part(array, high, low);
        quick(array, base - 1, low);
        quick(array, high, base + 1);
    }
}

/**
 *    对于 3 7 2 6 1 4 5 这个序列
 *    选择第一个数 3 作为基数, 用两个指针实现把比基数大的移到右边,比基础小的移到左边。
 *    (1)要先动 high指针,5 > 3 不用移动,所以 high--, 此时 4 > 3 high -- , 1 < 3
 *       就令 array[low] = array[high] (low 此时在 0 处)跳到2
 *    (2)再动 low 指针,1 < 3 所以 low++, 7 >3 所以 令array[high] = array[low],返回1
 *       上诉过程就是 3 7 2 6 1 4 5 ——>  1 7 2 6 1 4 5 (low = 0, high = 4) ->
 *       1 7 2 6 7 4 5(low = 1 high = 4) -> 1 2 2 6 7 4 5 (low = 1, high = 2) ->
 *       1 2 2 6 7 4 5(low = 2, high = 2)
 *       最后令array[low] = base;
 *
 *
 */
public static int part (int[] array, int high, int low) {
    // 选择第一个数作为基准数并定义base存放
    int base = array[low];
    while (low < high) {
        while (low < high && array[high] > base) {
            high--;
        } // 找到比 base 小的数退出循环,再进行赋值
        array[low] = array[high];
        while (low < high && array[low] < base) {
            low++;
        }
        array[high] = array[low];
    }
    array[high] = base;
    return high;
}

简单选择排序

  1. 算法思想

    每次选择一个最小的元素,然后与原位置上的元素进行交换

  2. 实现步骤

     /**
         * 简单选择排序(从小到大)
         * 每次选择一个最小的元素,然后与原位置上的元素进行交换
         */
        public static void chooseSmiple(int[] array) {
            for (int i = 0; i < array.length; i++) {
                int min = array[i];
                int key = i;
                for (int j = i; j < array.length; j++) {
                    if (min > array[j]) {
                        min = array[j];
                        key = j;
                    }
                }
                // 交换
                array[key] = array[i];
                array[i] = min;
            }
        }
    
    }
    

堆排序(占个位)

归并排序 (占个位)

整体代码

import javax.xml.bind.annotation.XmlInlineBinaryData;

/**
 * @author HelloWorld
 * @create 2021-04-07-20:38
 * @email 154803771@qq.com
 */
public class sort {
    /**
     * 排序算法
     * 全部按照从小到大的顺序排序
     */
    public static void main(String[] args) {
        int[] array = new int[]{4, 7, 8, 9, 1, 5, 3, 2, 6};
        // 直接插入排序
        insertDirectly(array);
        System.out.println();
        //折半插入排序
        array = new int[]{4, 7, 8, 9, 1, 5, 3, 2, 6};
        System.out.println("初始时:");
        inputArray(array);
        halfInsert(array);
        System.out.println("折半插入排序");
        inputArray(array);
        System.out.println();
        //冒泡排序
        array = new int[]{4, 7, 6, 2, 1, 5, 3, 9, 8};
        bubble(array);
        System.out.println();
        //快速排序
        array = new int[]{4, 7, 8, 9, 1, 5, 3, 2, 6};
        System.out.println("初始时:");
        inputArray(array);
        quick(array, array.length - 1, 0);
        System.out.println("快速排序后:");
        inputArray(array);
        System.out.println();
        // 简单选择排序
        array = new int[]{4, 7, 6, 2, 1, 5, 3, 9, 8};
        System.out.println("初始时:");
        inputArray(array);
        chooseSmiple(array);
        System.out.println("简单选择排序后:");
        inputArray(array);
        System.out.println();

    }
    public static void inputArray(int[] array) {
        for (int data : array) {
            System.out.print(data +" ");
        }
        System.out.println();
    }

    /**
     * 直接插入排序(从小到大)
     * 从第二位开始,依次向前比较,如果遇到比它大的移动位置
     */
    public static void insertDirectly(int[] A) {
        int[] array = A;
        System.out.println("初始:");
        inputArray(array);
        int len = array.length;
        for (int i = 1; i < len; i++) {

            // 0 到 i - 1 这个序列一定是有序的,若 array[i] > array[i - 1] 此时的元素已经在它应在的位置上
            // 所以只需要考虑当前元素在有序序列中的位置
            for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
                array[j] = array[j] ^ array[j - 1];
                array[j - 1] = array[j] ^ array[j - 1];
                array[j] = array[j] ^ array[j - 1];
            }
        }
        System.out.println("直接插入排序:");
        inputArray(array);
    }
    /**
     * 折半插入排序
     * 跟直接插入相比只是在查找位置时,采用折半查找。
     */
    public static void halfInsert(int[] A) {
        int[] array = A;
        int len = array.length;
        for (int i = 1; i < len ; i++) {
            // 存放当前value的值
            int value = array[i];
            // 定义 low 和high 确定查找的范围
            int low = 0;
            int high = i - 1;
            int middle;
            // 折半查找
            while (low <= high) {
                middle = (low + high) / 2;
                if (array[middle] > value) {
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            }

            //移位
            for(int j = i - 1; j >= high + 1; j--){
                array[j + 1] = array[j];
            }
            array[high + 1] = value;
        }
    }


    /**
     * 冒泡排序 (从小到大)
     * 每一次都从 i = 0开始,与相邻的下一个元素开始比较,遇到比它小的交换位置,直到数组有序为止
     * 第一个for 循环控制一共需要比较几轮  len - 1
     * 第二个for 循环控制每次比较的次数
     */
    public static void bubble(int[] A) {
        int[] array = A;
        System.out.println("初始:");
        inputArray(array);
        int len = array.length;

        // 设置flag 当不发生交换时,证明数组已经有序,直接退出循环

        for (int i = 1; i < array.length; i++) {
            boolean flag = true;
            for (int j = 0; j < len - i; j ++) {
                if (array[j] > array[j + 1]) {
                    array[j] += array[j + 1];
                    array[j + 1] = array[j] - array[j + 1];
                    array[j] = array[j] - array[j + 1];
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        System.out.println("冒泡排序:");
        inputArray(array);
    }
    /**
     * 快速排序
     * 每次选择一个数作为基数(一般都选第一个数),将所有比这个数大的放在这个数的右边,比它小的放左边
     * 对新产生的两个序列分别按上诉方法再次拆分
     */
    public static void quick(int[] array, int high, int low) {
        if (low < high) {
            int base = part(array, high, low);
            quick(array, base - 1, low);
            quick(array, high, base + 1);
        }
    }

    /**
     *    对于 3 7 2 6 1 4 5 这个序列
     *    选择第一个数 3 作为基数, 用两个指针实现把比基数大的移到右边,比基础小的移到左边。
     *    (1)要先动 high指针,5 > 3 不用移动,所以 high--, 此时 4 > 3 high -- , 1 < 3
     *就令 array[low] = array[high] (low 此时在 0 处)跳到2
     *     (2)再动 low 指针,1 < 3 所以 low++, 7 >3 所以 令array[high] = array[low],返回1
     *     上诉过程就是 3 7 2 6 1 4 5 ——>  1 7 2 6 1 4 5 (low = 0, high = 4) ->
     *     1 7 2 6 7 4 5(low = 1 high = 4) -> 1 2 2 6 7 4 5 (low = 1, high = 2) ->
     *     1 2 2 6 7 4 5(low = 2, high = 2)
     *     最后令array[low] = base;
     *
     *
     */
    public static int part (int[] array, int high, int low) {
        // 选择第一个数作为基准数并定义base存放
        int base = array[low];
        while (low < high) {
            while (low < high && array[high] > base) {
                high--;
            } // 找到比 base 小的数退出循环,再进行赋值
            array[low] = array[high];
            while (low < high && array[low] < base) {
                low++;
            }
            array[high] = array[low];
        }
        array[high] = base;
        return high;
    }
    /**
     * 简单选择排序(从小到大)
     * 每次选择一个最小的元素,然后与原位置上的元素进行交换
     */
    public static void chooseSmiple(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int min = array[i];
            int key = i;
            for (int j = i; j < array.length; j++) {
                if (min > array[j]) {
                    min = array[j];
                    key = j;
                }
            }
            // 交换
            array[key] = array[i];
            array[i] = min;
        }
    }

}


这篇关于排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程