高级排序--归并排序、快速排序

一、归并排序

原理很简单:将整个数据一分为二,再对每个子模块一分为二,一直分到还剩一个元素,然后再合并,在合并的过程中将其排好序。(注意这里需要另外开辟一个和原数组一样的数组的拷贝,合并的过程中将拷贝数组的对应元素排好序放到原数组上即可)

代码实现:
import java.util.Arrays;
/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-07 21:59
 **/
public class MergeSortTest {
    private MergeSortTest(){}
    public static void sort(int[] arr){
        sort(arr, 0, arr.length - 1);
    }
    private static void sort(int[] arr, int l, int r){
        if (l >= r){
            return;
        }else {
            int mid = l + (r - l) / 2;
            sort(arr, l, mid);
            sort(arr, mid + 1, r);
            // 小优化:已经排序的两个数组,如果左边数组的最右边(最大数)小于右边数组的
            // 最左边(最小)说明不必要归并了
            if (arr[mid] > arr[mid + 1]){
                merge(arr, l, mid, r);
            }
        }
    }
    // 合并两个有序的区间,使得合并后的新数组也为有序 arr[l, mid] 和 arr[mid + 1, r]
    private static void merge(int[] arr, int l, int mid, int r){
        // 开辟一个新数组---一份拷贝,用于将它里面的值赋值给原数组
        int[] temp = Arrays.copyOf(arr, arr.length);
        // 两个指针,i 指向l、j指向中间位置
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid){
                arr[k] = temp[j];
                j ++;
            }else if (j > r){
                arr[k] = temp[i];
                i ++;
            }else if (temp[i] <= temp[j]){
                arr[k] = temp[i];
                i ++;
            }else {
                arr[k] = temp[j];
                j ++;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,23,3,43,5,2,65,76,2,34,56,2,7,88,875};
        sort(arr);
        for (int a : arr) {
            System.out.println(a);
        }
    }
}

二、快速排序

1、指定一个元素,将小于这个元素的数放到它前面,大于它的数放到它后面;

2、分别对左右两个子数组进行递归排序。

/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-07 19:54
 **/
public class QuickSort2Test {
    private QuickSort2Test(){}
    public static void sort(int[] arr){
        sort(arr, 0, arr.length - 1);
    }
    private static void sort(int[] arr, int l, int r){
        if (l >= r){
            return;
        }
        int sigin = parition(arr, l, r);
        sort(arr, l, sigin - 1);
        sort(arr, sigin + 1, r);
    }
    // 在数组中找到一个元素,并且将大于这个元素的所有数字放到这个元素后面,小于这个元素的放到前面
    private static int parition(int[] arr, int l, int r){
        int i = l + 1, j = r;
        while (true){
            while (i <= j && arr[i] < arr[l]){
                i ++;
            }
            while (i <= j && arr[j] > arr[l]){
                j --;
            }
            if (i >= j){
                break;
            }
            swap(arr, i, j);
            i ++; j --;
        }
        swap(arr, l, j);
        return j;
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] arr = {2,4,1,32,44,5,12,3,21,76,3,45,1888,245,54,23};
        sort(arr);
        for (int a : arr) {
            System.out.println(a);
        }
    }
}

 


已有 0 条评论

    欢迎您,新朋友,感谢参与互动!