排序算法

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

分类

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. 算法思想

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

2. 实现

   /**
    * 折半插入排序
    * 跟直接插入相比只是在查找位置时，采用折半查找。
    */
   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;
        }
    }

}

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