实现数组排序的几种方法-蒲公英云

实现数组排序的几种方法

男娘i 2022-04-18 02:16 360阅读 0赞

冒泡排序

这里先介绍一下冒泡排序。

其原理就是相邻的两个元素进行比较，如果第一个元素大于第二个元素，则交换这两个元素的位置。如此两两比较然后交换，一轮下来，最大的元素会跑到最后的位置去。然后进行下一轮比较，最终就实现了排序。代码实现如下：

public static void main(String[] args) {

    int[] arr = new int[]{1, 8, 3, 2, 9, 7, 7, 25, 16};
    for (int i = 0; i < arr.length - 1; i++) {  //此处表示比较趟数
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + ", ");
    }
}

附上打印结果：

在这里插入图片描述

然后说说冒泡排序的改进版：如果在排序的时候，比较一趟就实现了全部排序呢，那么后面的排序还有必要进行吗？当然是no，所以可以怎么做呢，我们可以定义一个布尔类型的flag，每趟比较过后，查看是否完成了所有排序，如果完成了就直接结束。具体代码如下：

public static void arraySort(int[] a) {
        boolean flag;
        for (int i = 0; i < a.length - 1; i++) {  //此处表示比较趟数
            flag= false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = temp;
                    flag= true;
                }
            }
            if (!flag) return;
        }
    }

选择排序

第二种是第一个元素与其他所有元素进行比较，如果第一个元素大于其他元素，则交换位置。如此一轮下来，可以比较出最小的元素，并将其交换到第一个位置。如此循环往复，最终便可以实现排序。其实这种排序方法叫选择排序，代码如下：

public static void main(String[] args) {

    int[] arr = new int[]{1, 8, 3, 2, 9, 7, 7, 25, 16};
   for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + ", ");
    }
}

打印结果和上图是一样的。

快速排序

快速排序是冒泡排序的改进版，速度最快，但是相对没那么稳定。具体实现如下：

public static void quickSort(int[] a, int left, int right) {

    if (left > right) {
        return;
    }
    int i, j, temp;
    i = left;
    j = right;
    temp = a[left];     //temp为基准位
    while (i < j) {
        //先从右往左遍历
        //遍历的顺序取决于基准位的选取位置，要从基准位的对面开始遍历
        while(i < j && a[j] >= temp) {
            j--;
        }
        //然后从左往右遍历
        while (i < j && a[i] <= temp) {
            i++;
        }
        //交换位置
        if (i < j) {
            int s = a[i];
            a[i] = a[j];
            a[j] = s;
        }
    }
    //将基准位与i和j相等位置的数字交换
    a[left] = a[i];
    a[i] = temp;
    //递归调用左边部分数组
    quickSort(a, left, i - 1);
    //递归调用右边部分数组
    quickSort(a, j + 1, right);
}