美文网首页
快速排序

快速排序

作者: 巴巴呀呀 | 来源:发表于2022-04-20 16:23 被阅读0次

    import java.util.*;

    public class Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
    * 将给定数组排序
    * @param arr int整型一维数组 待排序的数组
    * @return int整型一维数组
    */
    public int[] MySort (int[] arr) {
    // quickSort(arr, 0, arr.length-1);
    // bubbleSort(arr);
    // selectSort(arr);
    // insertSort(arr);
    shellSort(arr);
    return arr;
    }

    // 希尔
    public void shellSort(int[] arr) {
        int step = arr.length / 2;
        while (step >= 1) {
            for (int i=step; i < arr.length; i++) {
                for (int j=i; j >= step; j -= step) {
                    if (arr[j] < arr[j-step]) {
                        swap(arr, j, j-step);
                    } else {
                        break;
                    }
                }
            }
            step /= 2;
        }
    }
    
    // 插入
    public void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j;
            for (j=i-1;j>=0;j--) {
                if (arr[j] > key) {
                    arr[j+1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+1] = key;
        }
    }
    
    // 选择
    public void selectSort(int[] arr) {
        for (int i = 0; i < arr.length -1; i++) {
            int min = arr[i];
            int minIndex = i;
            for (int j = i+1; j < arr.length; j ++) {
                if (arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }
    
    // 冒泡
    public void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            for (int j=0; j < arr.length-i-1;j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
    }
    
    // 快排
    public void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int key = arr[left];
        int i = left, j = right;
        while (i < j) {
            while (i < j && arr[j] >= key) j--;
            while (i < j && arr[i] <= key) i++;
            if (i < j) swap(arr, i, j);
        }
        swap(arr, left, i);
        quickSort(arr, left, i-1);
        quickSort(arr, i+1, right);
    }
    
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    

    }

    相关文章

      网友评论

          本文标题:快速排序

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