欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java 基础排序(冒泡、插入、选择、快速)算法回顾

程序员文章站 2022-06-13 11:28:37
java 基础排序(冒泡、插入、选择、快速)算法回顾 冒泡排序 插入排序 java private static void insertSort(int[] array) { int j; //从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的 for (int i = ......

java 基础排序(冒泡、插入、选择、快速)算法回顾

  • 冒泡排序
private static void bubblesort(int[] array) {
        int temp;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }

        print(array);
    }
  • 插入排序
private static void insertsort(int[] array) {
        int j;
        //从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];//记录要插入的数据
            j = i;
            //从已经排序的序列最右边的开始比较,找到比其小的数
            while (j > 0 && tmp < array[j - 1]) {
                //向后挪动
                array[j] = array[j - 1];
                j--;
            }
            //存在比其小的数,插入
            array[j] = tmp;
        }

        print(array);
    }
  • 选择排序
private static void choisesort(int[] array) {
        //记录目前能找到的最小值元素的下标
        int min;
        //经过n-1轮比较
        for (int i = 0; i < array.length - 1; i++) {
            min = i;
            //每轮需要比较的次数
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }

            //将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }

        print(array);
    }
  • 快速排序

 /**
     * 快速排序
     *
     * @param array
     * @param left
     * @param right
     */
    private static void quicksort(int[] array, int left, int right) {
        if (left >= right) return;
        int pivot = partition(array, left, right);
        quicksort(array, left, pivot - 1);
        quicksort(array, pivot + 1, right);

    }

    /**
     * 数组划分
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] array, int left, int right) {
        int pivotkey = array[left];
        while (left < right) {
            while (left < right && array[right] >= pivotkey) {
                right--;
            }
            array[left] = array[right];

            while (left < right && array[left] <= pivotkey) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivotkey;
        return left;
    }
  • 测试
private static void print(int[] array) {
        for (int i = 0; i < array.length; i++) {
            system.out.printf(array[i] + " ");
        }
    } 

 public static void main(string[] args) {
        int[] array = {4, 2, 8, 9, 5, 7, 6, 1, 3};
        system.out.println("原始数据:");
        print(array);
        system.out.println("\r\n");
        system.out.println("冒泡排序:");
        bubblesort(array);
        system.out.println("\r\n");
        system.out.println("选择排序:");
        choisesort(array);
        system.out.println("\r\n");
        system.out.println("插入排序:");
        insertsort(array);

         int array[] = {65, 58, 95, 10, 57, 62, 13, 106, 78, 23, 85};

        system.out.println("快速排序前:" + arrays.tostring(array));

        quicksort(array, 0, array.length - 1);

        system.out.println("快速排序后:" + arrays.tostring(array));
    }