美文网首页
排序算法代码实现

排序算法代码实现

作者: wuhuaguo丶 | 来源:发表于2019-05-07 16:19 被阅读0次

    归并排序

        /*
         * 归并排序(从上往下)
         * 
         * 参数说明: a -- 待排序的数组 start -- 数组的起始地址 endi -- 数组的结束地址
         */
        public void Sort(int[] a, int start, int end) {
            if (a == null || start >= end)
                return;
    
            int mid = (end + start) / 2;
            Sort(a, start, mid); // 递归排序a[start...mid]
            Sort(a, mid + 1, end); // 递归排序a[mid+1...end]
    
            // a[start...mid] 和 a[mid...end]是两个有序空间,
            // 将它们排序成一个有序空间a[start...end]
            merge(a, start, mid, end);
        }
        /*
         * 将一个数组中的两个相邻有序区间合并成一个
         * 
         * 参数说明: a -- 包含两个有序区间的数组 start -- 第1个有序区间的起始地址。 mid --
         * 第1个有序区间的结束地址。也是第2个有序区间的起始地址。 end -- 第2个有序区间的结束地址。
         */
        public void merge(int[] a, int start, int mid, int end) {
            int[] tmp = new int[end - start + 1]; // tmp是汇总2个有序区的临时区域
            int i = start; // 第1个有序区的索引
            int j = mid + 1; // 第2个有序区的索引
            int k = 0; // 临时区域的索引
            // 类似于合并两个有序链表,当两个有序链表都有数据时,比较这两个链表的数据,并将小的数据放到新开辟出的空间中
            while (i <= mid && j <= end) {
                if (a[i] <= a[j])
                    tmp[k++] = a[i++];
                else
                    tmp[k++] = a[j++];
            }
            // 防止两个数组一个排完了,另一个还没有排完,将剩下的那个数组的值接在后面。
            while (i <= mid)
                tmp[k++] = a[i++];
    
            while (j <= end)
                tmp[k++] = a[j++];
    
            // 将排序后的元素,全部都整合到数组a中。
            for (i = 0; i < k; i++)
                a[start + i] = tmp[i];
    
            tmp = null;
        }
    

    快速排序

        /*
         * 快速排序
         * 
         * 参数说明: a -- 待排序的数组 l -- 数组的左边界(例如,从起始位置开始排序,则l=0) r --
         * 数组的右边界(例如,排序截至到数组末尾,则r=a.length-1)
         */
        public static void quickSort(int[] a, int l, int r) {
            if (l < r) {
                int i, j, x;
    
                i = l;
                j = r;
                x = a[i];
                while (i < j) {
                    while (i < j && a[j] > x) {
                        j--; // 从右向左找第一个小于x的数
                    }
                    if (i < j) {
                        a[i++] = a[j];
                    }
                    while (i < j && a[i] < x) {
                        i++; // 从左向右找第一个大于x的数
                    }
                    if (i < j) {
                        a[j--] = a[i];
                    }
                }
                a[j] = x;
                quickSort(a, l, i - 1); /* 递归调用 */
                quickSort(a, i + 1, r); /* 递归调用 */
            }
        }
    

    相关文章

      网友评论

          本文标题:排序算法代码实现

          本文链接:https://www.haomeiwen.com/subject/avqyoqtx.html