实现数组排序的几种方法

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

**冒泡排序**

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

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

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] + ", ");
            }
        }

附上打印结果：

![在这里插入图片描述][2018110711015550.png]

然后说说**冒泡排序的改进版**：如果在排序的时候，比较一趟就实现了全部排序呢，那么后面的排序还有必要进行吗？当然是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;
            }
        }

**选择排序**

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

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] + ", ");
            }
        }

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

**快速排序**

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

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);
        }

[更加详细介绍请参考这里][Link 1]

更新于2018.11.30

[2018110711015550.png]: /images/20220418/0671443fea1b4d5295657dc31c3e850c.png
[Link 1]: https://blog.csdn.net/as02446418/article/details/47395867