黑马程序员技术交流社区

标题: 数组从小到大排序 [打印本页]

---

作者: 1418630932    时间: 2019-5-24 20:30
标题: 数组从小到大排序
关于数组排序的方法总结

1.选择排序
   选择排序是一种常用的数组排序方法
   如果要从小到大排序
   首先数组的第一个元素 依次与第2，3，4......个元素依次比较  
   如果前者比后者要大 就交换两个元素  这样可以保证第一个元素是最小的
   再从第二个元素开始 依次比较 第3，4，5.......个元素 可以保证第二个元素是数组
第二小的
以此类推
代码实现
public static void xzpx(int[] arr) {
    for (int i = 0; i < arr.length-1; i++) { //控制循环次数
        for (int j = i + 1; j < arr.length; j++) { //控制比较的index
            if (arr[i] > arr[j]) {
                int tmp = 0;
                tmp = arr[i];  //中间变量
                arr[i] = arr[j];//交换位置
                arr[j] = tmp;
            }

        }
    }
}




2.冒泡排序

冒泡排序也是一种常用排序方法
如果要把数组从小到大排序
通过第n个元素与第n+1个元素比较
如果如果前者比后者大  则交换两者位置
第一次循环比较数组第1个元素和第2个元素 如果第一个比第二个大 就交换元素位置
然后再比较第二个元素和第三个元素的位置 .........
第一次循环结束数组的最后一个元素 就是最大值
第二次循环结束数组的倒数第二个元素就是第二大值
以此类推

就像冒泡 大的元素会逐渐浮上来

代码实现
public static void mppx(int[] arr) {
    for (int i = 0; i < arr.length-1; i++) { //定义循环次数
        for (int j = 0; j < arr.length-i-1; j++) { //定义比较元素的index
            if (arr[j] > arr[j+1]) {
                int tmp = 0;
                tmp = arr[j];  //中间变量
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}
3快速排序
Arrays.sort();
通过阅读JDK文档我发现 java有一个类Arrays 其中有一个方法叫做sort()
文档解释如下
public static void sort(int[] a)
对指定的 int 型数组按数字升序进行排序。该排序算法是一个经过调优的快速排序法，改编自 Jon L. Bentley 和 M. Douglas McIlroy 合著的 Engineering a Sort Function", Software-Practice and Experience Vol. 23(11) P. 1249-1265 (November 1993)。此算法在许多数据集上提供 n*log(n) 性能，这导致其他快速排序会降低二次型性能。
参数：
a - 要排序的数组

可以看到java对数组排序 使用的是一种快速排序的算法 效率非常之高

快速排序采用的是二分+递归的形式排序
对一个数组 任意取一个元素 一般取数组第一个元素
   int[] arr = {5,3,10,7,1};

当我们取5时  快速排序 会对数组进行排序   大于等于5的元素放到5的右边 小于5的元素放到5的左边
第一次二分排序
[3,1,5,10,7]
这时候 数组被分成了三部分    3，1组成了第一部分  5 是第二部分 10，7是第三部分
这时候只需要再对第一部分和第三部分采用二分的排序 第一部分就被分为了 1，3 第三部分就被分为了 7，10
此时 数组的排列就是 1，3，5，7，10
递归的停止循环的条件是数组是数组满足从小到大排序

代码实现
public static void kspx(int[] arr,int top,int end){
    if (top>end){//递归结束条件 当参数中的数组是从小到大排序的时候 top++ end-- 之后 就不符合top>end
        return;
    }

    int temp=arr[top];//需要比较的数组元素
    int i=top;
    int j=end;
    while (i<j){
        while(temp<=arr[j]&&i<j){//从数组右边开始比较 当遇到小于temp的元素 停止循环
            j--;
        }
        while(temp>=arr[i]&&i<j){//从数组左边开始比较 当遇到大于 temp的元素 停止循环
            i++;
        }
        if (i<j){   //i位置和j位置元素互换   这样可以实现i位置的元素小于等于temp  j位置的元素大于等于temp
            int a=arr[i];
            arr[i]=arr[j];
            arr[j]=a;
        }
    }
    arr[top]=arr[i];   //while循环结束的条件是i<j   当循环结束的时候 说明i==j
    arr[i]=temp;        //此时调换top元素与i元素的位置 形成了i元素左边<=i元素  i元素右边>=i元素

    kspx(arr, top, i-1);//左边数组调用方法
    kspx(arr, i+1, end);//右边数组调用方法
}




为了验证三种排序方法的运行效率 统计了方法消耗的时间

冒泡排序时长统计示例：
public static void main(String[] args) {
   
    int[] arr = new int[10000];
    for (int i=0;i<arr.length;i++){//给数组中的10000个元素赋值
        Random random=new Random();
        int j = random.nextInt(10000);//j是一个0-9999的随机数
        arr[i]=j;
    }
Long timeBefor=System.currentTimeMillis();//获取运行前的时间戳
    mppx(arr);//对数组冒泡排序
    Long timeAfter=System.currentTimeMillis();//获取运行后的时间戳
    System.out.println(timeAfter-timeBefor);//计算算法耗时(毫秒)
}

选择排序 对一个10000长度的数组排序  10次执行平均消耗时长  325ms
冒泡排序 对一个10000长度的数组排序  10次执行平均消耗时长  320ms
快速排序 对一个10000长度的数组排序  10次执行平均消耗时长  4 ms
由此可见 快速排序是一个非常快的排序方法

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2