请选择 进入手机版 | 继续访问电脑版
查看: 1162|回复: 0

【算法分享】算法之常见排序算法-冒泡排序、归并排序、快速排序

[复制链接]

  离线 

 成长值: 2260

  • TA的每日心情
    开心
    4 天前
  • 签到天数: 76 天

    [LV.6]常住居民II

    346

    主题

    402

    帖子

    2452

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    2452
    发表于 2019-10-4 22:08:09 | 显示全部楼层 |阅读模式
    引言
        对于编程中琳琅满目的算法,本人向来是不善此道也不精于此的,而说起排序算法,也只是会冒泡排序。还记得当初刚做开发工作面试第一家公司时,面试官便让手写冒泡排序(入职之后才知道,这面试官就是一个冒泡排序"病态"爱好者,逢面试必考冒泡排序-__-)。后来看吴军的一些文章,提到提高效率的关键就是少做事情不做无用功,便对这不起眼的排序算法有了兴趣。刚好今天周末有闲,遂研究一二,与各位道友共享。
        了解了思想之后,再用代码实现相对就会容易很多。此处就再借用一个直观一点的例子来说明归并与快排二者的区别。假设有1000个学生,想对他们的成绩进行排序。方法1借用归并排序的思想,具体这样做:将这1000个人分成10组,将每组的100人进行排序,排完之后再在各组之间从小到大依次进行比较,最后得到整个的成绩排名。方法2借用快速排序的思想,具体需这样做:将1000个人也是分成10组,但是是按分数段分,0-10分的放在一组,10-20分的放在一组,20-30分的放在一组,依次类推,分完组之后再在各个小组中进行排序,而当你合并各个小组时,只需将其按从小到大的顺序直接合并就行,无需跟方法1一样将各小组中的数据取出来跟其他小组中的数据挨个比较。看到这里,想必各位道友对快排比归并排序还要快一些的原因就有了解了。
    正文
    归并排序
    // 归并排序
        public static void mergeSort (int[] arr) {
            // 建一个临时数据来存放数据
            int[] temp = new int[arr.length];
            mergeSort(arr, 0, arr.length - 1, temp);
        }

        private static void mergeSort(int[] arr, int left, int right, int[] temp) {
            if (left < right) { // 如果起始下标跟结束下标差值小于1,则不进行操作
                int mid = (left + right) / 2;
                mergeSort(arr, left, mid, temp); // 分组,将左边分为一组,递归调用进行排序
                mergeSort(arr, mid+1, right, temp); // 将右边分为一组
                merge(arr, left, mid, right, temp); //将左右分组合并
            }
        }

        private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
            int i = left; // 定义左指针
            int j = mid + 1; // 定义右指针
            int t = 0; // 给temp临时数组用的指针
            while (i <= mid && j <= right) { // 设置左右指针的移动边界
                if (arr[i] <= arr[j]) { // 此处是升序,故谁小谁先赋给临时数组
                    temp[t++] = arr[i++];
                } else {
                    temp[t++] = arr[j++];
                }
            }
            while (i <= mid) { // 如果左边有剩余,则放在temp中
                temp[t++] = arr[i++];
            }
            while (j <= right) { // 如果右边有剩余,依次放入temp中
                temp[t++] = arr[j++];
            }
            t = 0;
            // 此时temp中已经是arr数组中下标从left到right之间排好序的数据了,因为temp每次都是从0开始赋值,所以需将排好序的数放回arr的对应位置
            while (left <= right) {
                // 将left到right之间排好序的数据放回arr中,此时left到right之间的数就是最终排好序的数
                arr[left++] = temp[t++];
            }
        }

    快速排序

    // 快速排序
        public static void quickSort (int[] arr, int left, int right) {
            // 先将异常情况处理掉
            if (arr == null || arr.length < 2) {
                return;
            }
            if (right <= left) {
                return;
            }
            if (right - left == 1 && arr[left] <= arr[right]) {
                return;
            }
            // 取第一个数为基准数(基数取哪个都行,此处是为了方便)
            int index = arr[left];
            int i = left + 1; // 左指针
            int j = right; // 右指针
            while (i < j && i < right && j > left) { // 设置指针的移动边界
                while (arr[j] > index && j > left) {j--;} // 找到从右边数第一个比index小的数
                while (arr[i] < index && i < right) {i++;} // 找到从左边数第一个比index大的数
                if (i < j) { // 交换这两个数  如果i == j,说明二者定位到了同一个位置,则不用交换;如果i > j,说明二者已经相遇然后背向而行了,也不交换
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            // 执行完上面循环后,arr已经是左边比index小,右边比index大的数组了,只是基准数仍在基准位置left处,需放到它应该在的位置
            if (j != left && arr[j] != arr[left]) {
                // j最后停留位置的数,肯定是一个小于等于index的值,所以如果不是同一个位置的话,直接将二者调换一下位置即可
                int temp = arr[j];
                arr[j] = arr[left];
                arr[left] = temp;
            }
            quickSort(arr, left, j-1); // 将基准数左边排序
            quickSort(arr, j+1, right); // 将基准数右边排序
        }

    温馨提示:
    1、在论坛里发表的文章仅代表作者本人的观点,与本网站立场无关。
    2、论坛的所有内容都不保证其准确性,有效性,时间性。阅读本站内容因误导等因素而造成的损失本站不承担连带责任。
    3、根据二○○二年一月一日《计算机软件保护条例》规定:为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬!鉴于此,也希望大家按此说明研究软件!谢谢
    4、若因线路及非本站所能控制范围的故障导致暂停服务期间造成的一切不便与损失,论坛不负任何责任。
    5、注册会员通过任何手段和方法针对论坛进行破坏,我们有权对其行为作出处理。并保留进一步追究其责任的权利。
    6、本站所有资源来自互联网,版权归原作者所有,所有资源仅供于学习、交流研究,请于下载24小时之后删除!
    7、当您在浏览本站时,发现有您自己创作的原创资源时侵犯了您的合法资源时,请您及时联系管理员,邮箱:2550721739@qq.com,我们会及时处理!
    使用 高级模式(可批量传图、插入视频等)
    您需要登录后才可以回帖 登录 | 立即注册