简介

　　Java中的数组是一种数据集合，里面可以存储若干数据元素。有时我们需要对这些数据元素进行排序，找出数组中的最大值、最小值，或者是按降序或升序对数组进行排列，这些需求都需要我们能够对数组进行排序。但我们要注意，对数组排序会修改数组本身，即数组里元素的内存指向会发生改变。

　　对数组进行排序是程序中很常见的需求。如果我们想要实现数组排序，可以利用数据结构中的某些排序算法来进行实现，比如著名的冒泡排序、选择排序等，当然也可以利用Java自带的Arrays.sort()方法来实现。接下来壹哥就针对这几种实现方案，给大家设计几个实现案例。

　　冒泡排序(重点)

　　2.1 简介

　　冒泡排序的核心实现思路，就是把数据元素按照从下到上，两两进行比较。所以冒泡排序的特点是，每一轮循环后，最大的一个数被交换到末尾。因此，下一轮循环可以“刨除”最后的数，每一轮循环都比上一轮循环的结束位置靠前一位。冒泡排序整体可以分为两种情况，即升序排列和降序排列。

　　升序排列的实现思想：

　　1.将数组中相邻的两个数据元素进行比较，如果前面一个元素比后面的大，就把两者交换位置(一轮比较);

　　2.然后将上面的操作进行循环(比较n-1轮)。

　　排列过程如下图所示：

　　降序排列的实现思想：

　　1.将数组中相邻的两个数据元素进行比较，如果前面一个元素比后面的小，就把两者交换位置(一轮比较);

　　2.然后将上面的操作进行循环(比较n-1轮)。

　　2.2 基本实现

　　大家要注意，面试时经常会让我们手写冒泡排序和选择排序等算法，你必须牢牢地记住相关的代码实现哦。

　　public class Demo09 {

　　public static void main(String[] args) {

　　// 冒泡排序--基本实现

　　//待排序的数组

　　int[] arr = { 1, 3, 46, 22, 11 };

　　//控制需要比较几轮

　　for (int i = 0; i < arr.length; i++) {

　　//控制每一轮的比较次数

　　for (int j = 0; j < arr.length - 1; j++) {

　　//如果前面的比后面的数字大，则两者就进行交换

　　if (arr[j] > arr[j + 1]) {

　　//两数交换，需要一个“第三方”，好比两杯水互换，需要第三个杯子。

　　//交换两个变量的值，必须借助一个临时变量。

　　//定义一个新的临时变量，将数组中的前面的元素先赋值给临时变量

　　int temp = arr[j];

　　//后面的值赋值到前面的位置上

　　arr[j] = arr[j + 1];

　　//再将临时变量的值赋值到后面的位置上

　　arr[j + 1] = temp;

　　}

　　}

　　}

　　//遍历排序后的数组

　　for(int i=0;i<arr.length;i++) p="" {<="">

　　System.out.print(arr[i]+"\t");

　　}

　　}

　　}

　　这种实现方式比较容易理解，但并不是最优的实现方案，因为这种方案需要比较的次数较多。我们可以进一步对该方案进行优化，将比较的次数降下来，请继续往下看。

　　2.3 优化次数

　　public class Demo10 {

　　public static void main(String[] args) {

　　// 冒泡排序--优化比较次数

　　// 待排序数组

　　int[] arr = { 1, 3, 46, 22, 11 };

　　for (int j = 0; j < arr.length; j++) { //控制轮数

　　for (int i = 0; i < arr.length - 1 - j; i++) {//控制每一轮的次数

　　if(arr[i] > arr[i+1]) {

　　int temp = arr[i];

　　arr[i] = arr[i+1];

　　arr[i+1] = temp;

　　}

　　}

　　}

　　//遍历排序后的数组

　　for(int i=0;i<arr.length;i++) p="" {<="">

　　System.out.print(arr[i]+"\t");

　　}

　　}

　　}

　　本案例同样也不是最优的实现方案，我们也可以对该实现方案进行优化。

　　2.4 优化轮数

　　在本案例中，会对比较的轮数进行优化。

　　/**

　　@author 一一哥Sun

　　QQ：2312119590

　　CSDN、掘金、知乎找我哦

　　*/

　　public class Demo11 {

　　public static void main(String[] args) {

　　// 冒泡排序--优化比较轮数

　　// 待排序数组

　　int[] arr = { 1, 3, 46, 22, 11 };

　　for (int j = 0; j < arr.length - 1; j++) { //轮数

　　//假设这一轮已经拍好序，设置一个标签进行记录

　　boolean flag = true;

　　for (int i = 0; i < arr.length - 1 - j; i++) {//每一轮比较的次数

　　if(arr[i] > arr[i+1]) {

　　//更改是否比较过的标签

　　flag = false;

　　int temp = arr[i];

　　arr[i] = arr[i+1];

　　arr[i+1] = temp;

　　}

　　}

　　//如果本轮已排序好，则直接跳过，避免没必要的比较。

　　if(flag) {

　　break;

　　}

　　}

　　//遍历排序后的数组

　　for(int i=0;i<arr.length;i++) p="" {<="">

　　System.out.print(arr[i]+"\t");

　　}

　　}

　　}

　　这种实现方案，可以说是三种方案中最优的一种。

　　选择排序(重点)

　　3.1 简介

　　选择排序的核心实现思路，是随机确定一个标志位(一般为第一个数字)作为最小数，然后向后遍历，找到比标志位更小的数字后，便与标志位互换位置，并更新最小数。选择排序同样可以进行升序或降序排列。

　　选择排序升序思路：

　　1.将当前位置上的数，与它后面的每个数进行比较，选择出最小的那个数，交换到当前位置;

　　2.循环选择当前位置上的数。

　　选择排序降序思路：

　　1.将当前位置上的数，与它后面的每个数进行比较，选择出最大的那个数，交换到当前位置;

　　2.循环选择当前位置上的数。

　　4. Arrays.sort方法

　　以上两种排序算法，实现起来是比较复杂的，但在面试时，基本上都要求我们能够手写出冒泡排序和选择排序，大家一定要把代码看懂哦。但如果我们想快速实现排序，其实可以使用Java自带的API方法进行实现，这个会更简单。

　　4.1 简介

　　Arrays工具类主要用于对数组进行排序、查找、填充、比较等的操作，该类存在于java.util包下，所以我们使用的第一步就是要先进行导包: import java.util.Arrays;

　　其中Arrays.sort()是Arrays类中的一个静态方法，用于对数组进行排序，我们可以直接调用。该方法有如下几种重载形式：

　　●sort(T[] a)：对指定T型数组按数字升序排序;

　　●sort(T[] a, int formIndex, int toIndex)：对指定T型数组中[formIndex,toIndex)数据按数字升序排序;

　　●sort(T[] a, Comparator c): 依据比较器对T型数组进行排序;

　　●sort(T[] a, int formIndex, int toIndex, Comparator c): 依据比较器产生的顺序对T型数组中的[formIndex,toIndex)进行排序。