排序

常见排序算法

插入排序：直接插入排序、希尔排序

直接插入排序

• 思路
  • 插入第i个对象时，前面的V[0]，V[1]，...，V[i-1]都已经排好序
  • 循环遍历前面的序列，比较V[i]与每个值的大小
  • 找到插入位置，插入V[i]，原位置上元素后移
• 代码

public void straightInsertSort(int[] seqList){
    // 插入次数与数组长度相同，而当只有一个元素时默认有序，所以从第二个元素开始选择插入
    for(int i = 1; i<seqList.length; i++){
        // 第i位与[0,i-1)位比较大小，从第i-1位向前遍历
        for(int j = i-1; j>=0; j--){
            if(seqList[j+1] < seqList[j])
                swap(seqList,j+1,j);
        }
    }
}
private static void swap(int[] seqList,int i, int j){
    int temp = seqList[i];
    seqList[i] = seqList[j];
    seqList[j] = temp;
}

希尔排序

• 思路
  • 取一个正整数 d < n
  • 将所有相隔d的记录放于同一组，进行直接插入排序
  • 然后使 d = d/2 或 d = d/3+1，重复上述分组和排序
  • 直至d = 1，即所有记录放进同一个组中排序为止
  • 注意：d取值一般为奇数或质数，同时d最后必须为1
• 代码

public void shellSort(int[] seqList, int step){
    // 直到步长为1时，停止
    while(step != 1){
        step /= 2;
        // 排序次数为步长长度
        for(int i = 0; i<step; i++){
            // 直接插入排序：以固定步长找到相应序列
            for(int j = i+step; j < seqList.length; j+=step){
                // 第j位与[0,j-step)位一一比较
                for(int k = j-step; k >= 0; k-=step){
                    if(seqList[k + step] < seqList[k])
                        swap(seqList,k+step,k);
                }
            }
        }
    }
}
private static void swap(int[] seqList,int i, int j){
    int temp = seqList[i];
    seqList[i] = seqList[j];
    seqList[j] = temp;
}

交换排序：冒泡排序、快速排序

冒泡排序

• 思路
  • 循环i次，每次将最大值的放到最后一位
  • 每次循环中，第1个与第2个比较，若逆序，则交换，第2个与第3个比较，重复，直到第n-1个与第n个比较
• 代码

public void bubbleSort(int[] seqList){
    // 循环次数为序列长度
    for(int i = 0; i < seqList.length; i++){
        boolean flag = true;
        // 两两比较，较大值不断后移（尾部为已排序好的序列）
        for(int j = 0; j < seqList.length - 1 - i;j++){
            if(seqList[j+1] < seqList[j]){
                swap(seqList,j+1,j);
                flag = false;
            }
        }
        if(flag)//若比较过程中，未发生交换，则说明已经排列好，可提前结束循环
            break;
    }
}
private static void swap(int[] seqList,int i, int j){
    int temp = seqList[i];
    seqList[i] = seqList[j];
    seqList[j] = temp;
}

快速排序

• 思路
  • 一趟排序将待排序序列分为两部分，一部分均比另一部分小
  • 再对这两部分排序，再分，直到整个序列有序
  • 即递归，从left和right中取一基准值，依次对比，每次确定一个值的最终位置。终止条件是left == right
• 代码

public void quickSort(int[] seqList, int left, int right){
    if(left < right){
        int middle = partition(seqList,left,right);
        quickSort(seqList,left,middle-1);
        quickSort(seqList,middle+1,right);
    }
}
private static int partition(int[] seqList, int left, int right){
    int pivotkey = seqList[left];
    // 左右、左右遍历与基准值比较，直到左右相遇
    while(left < right){
        // 从右边开始找，若大于等于基准值则继续向左，若小于则终止
        while(left < right && seqList[right] >= pivotkey)
            right--;
        seqList[left] = seqList[right];//left位置=右边小于基准值的数
        // 从左边开始找，若小于等于基准值则继续向右，若大于则终止
        while(left < right && seqList[left] <= pivotkey)
            left++;
        seqList[right] = seqList[left];//right位置=左边大于基准值的数
    }
    seqList[left] = pivotkey;//基准值回位
    return left;
}

选择排序：直接选择排序、堆排序

堆排序

• 前提需知

堆的定义：

• 大顶堆：每个节点的值都大于或等于其左右孩子节点的值
• 小顶堆：每个节点的值都小于或等于其左右孩子节点的值

对堆的节点按层编号，映射到数组中：

• 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
• 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

• 排序思路

  1. 构造初始堆。将给定的无序数组构造成一个大顶堆
  2. 最大值沉底。交换堆顶元素与末尾元素，使末尾元素最大，末尾标记指针前移
     • 由于堆顶沉底，堆结构被破坏，因此继续调整堆
     • 调整完成后，再交换堆顶与末尾元素，得到第二大元素
     • 重复进行交换、重建，最终使得整个序列有序

• 代码

public void heapSort(int[] arr){
    // 构造初始最大堆：从第一个非叶子节点从下至上，从左至右调整结构
    for(int i = arr.length/2; i>=0; i--){
        heapify(arr, i, arr.length);
    }
    // 交换堆顶与末尾元素 + 调整堆结构 
    for(int j = arr.length-1; j>0; j--){
        swap(arr,0,j);// 交换堆顶与末尾元素
        heapify(arr,0,j);// 调整堆结构 
    }
}

public void heapify(int[] arr, int i, int len){
    int left = 2*i + 1; // 二叉树的左节点位置
    int right = 2*i + 2;// 二叉树的右节点位置
    int max = i;// 默认根节点为最大值
    // 当左节点还未到达末尾时，左节点如果大于根节点
    if(left < len && arr[left] > arr[max]){
        max = left;
    }
    // 当右节点还未到达末尾时，右节点如果大于根节点
    if(right < len && arr[right] > arr[max]){
        max = right;
    }
    // 判断根节点位置是否更换过，若更换，则交换位置，继续调整堆结构
    if(max != i){
        swap(arr,i,max);
        heapify(arr,max,len);
    }
}

private void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

归并排序

• 思路
  • 分：将无序序列拆分成类似完全二叉树的结构（采用递归或迭代），递归深度为log2n
  • 治：将两个已经有序的子序列合并成一个
• 代码

public void mergeSort(int[] arr){
    // 排序前，先建好长度等于原数组长度的临时数组，避免递归时频繁开辟空间
    int[] res = new int[arr.length];
    sort(arr, 0, arr.length-1, res);
}

private void sort(int[] arr, int left, int right, int[] res){
    if(left < right){
        int mid = (left+right)/2;
        sort(arr, left, mid, res);// 左边归并排序，使左子序列有序
        sort(arr, mid+1, right, res);// 右边归并排序，使右子序列有序
        merge(arr, left, mid, right, res);
    }
}

private void merge(int[] arr, int left, int mid, int right, int[] res){
    int tempLeft = left;// 左序列指针
    int tempRight = mid+1;// 右序列指针
    int tempRes = 0;// 临时结果数组指针
    
    // 左右序列元素一一比较，较小值加入结果数组中对应位置
    while(tempLeft<=mid && tempRight<=right){
        if(arr[tempLeft] <= arr[tempRight]){
            res[tempRes++] = arr[tempLeft++];
        }else{
            res[tempRes++] = arr[tempRight++];
        }
    }
    // 若左序列还有剩余元素，则全部填充进结果数组中
    while(tempLeft <= mid){
        res[tempRes++] = arr[tempLeft++];
    }
    // 若右序列还有剩余元素，则全部填充进结果数组中
    while(tempRight <= right){
        res[tempRes++] = arr[tempRight++];
    }
    // 遍历结果数组，将其元素全部拷贝到原数组中
    tempRes = 0;
    while(left <= right){
        arr[left++] = res[tempRes++];
    }
}

题目

数组中重复数字

public int duplicate (int[] numbers) {
    // write code here
    Set<Integer> set = new HashSet<>();
    for(int i = 0; i<numbers.length; i++){
        if(!set.add(numbers[i]))
            return numbers[i];
    }
    return -1;
}

数组中最小的K个数（堆排序）

• 先排序，再遍历

public ArrayList<Integer> GetLeastNumbers(int [] input, int k) {
    ArrayList<Integer> res = new ArrayList<>();
    // 特殊情况
    if(k > input.length)
        return res;
    // 先排序
    Arrays.sort(input);
    // 再遍历排序好的序列，得到最小的k个数
    for(int i = 0; i<k; i++){
        res.add(input[i]);
    }
    return res;
}

• 堆排序

public ArrayList<Integer> GetLeastNumbers(int [] input, int k) {
    ArrayList<Integer> res = new ArrayList<>();
    // 特殊情况
    if(k > input.length || k == 0)
        return res;
    // 创建最大堆
    PriorityQueue<Integer> queue = new PriorityQueue<>(
        (num1, num2) -> num2 - num1
    );
    // 先向最大堆中存入前k个值
    for(int i = 0; i < k; i++){
        queue.offer(input[i]);
    }
    // 遍历序列后面的元素
    // 与堆顶元素判断，若小于堆顶元素，则说明其是最小k个数
    //    移除堆顶元素，将此元素加入堆中
    for(int i = k; i<input.length; i++){
        if(queue.peek() > input[i]){
            queue.poll();
            queue.offer(input[i]);
        }
    }
    // 将堆中元素转化成数组
    for(int i = 0; i < k; i++){
        res.add(queue.poll());
    }
    return res;
}

数据流的中位数

ArrayList<Integer> list = new ArrayList<>();
public void Insert(Integer num) {
    list.add(num);
}

public Double GetMedian() {
    Collections.sort(list);
    int n = list.size();

    if(n%2 == 0){
        return (double)(list.get(n/2-1)+list.get(n/2))/2;
    }else{
        return (double)list.get(n/2);
    }
}

数组中的逆序对（归并排序）

• 暴力遍历：超时

public int InversePairs(int [] array) {
    // 暴力遍历:超时
    int count = 0;
    for(int i = 0; i<array.length-1; i++){
        for(int j = i+1; j<array.length; j++){
            if(array[i] > array[j])
                count++;
        }
    }
    return count%1000000007;
}

• 归并排序

int count = 0;
public int InversePairs(int [] array) {
    // 归并排序：分而治之
    // 分：将数组分为两个子数组，两个子数组分为四个，依次向下分，直到不可再分
    // 并：从最小的数组，按顺序合并，从小到大或从大到小，依次向上并，最后得到合并的顺序数组
    // 此题：合并{4,5}和{1,2}，首先判断4>1，则可知逆序对为2（(4,1),(5,1)）
    //    此时利用临时数组，将1存放进去，再判断4>2，又可知逆序对为2（(4,2),(5,2)）
    //    此时右边子数组已空，则将左边剩余元素全部放入临时数组
    //    最后将临时数组中元素放进原数组对应位置
    //    接着向上合并
    if(array.length < 2)
        return 0;
    mergeSort(array,0,array.length-1);
    return count;

}
private void mergeSort(int[] array, int left, int right){
    // 找分割点
    int mid = left + (right-left)/2;
    if(left < right){
        // 左子数组拆分
        mergeSort(array,left,mid);
        // 右子数组拆分
        mergeSort(array,mid+1,right);
        // 归并
        merge(array,left,mid,right);
    }
}

public void merge(int[] array,int left,int mid,int right){
    // 创建临时数组
    int[] tempArr = new int[right-left+1];
    // 创建临时数组初始指针
    int i = 0;
    // 记录原数组中的起点下标值
    int start = left;
    // 记录初始时的左右子数组起始位置
    int tempLeft = left;
    int tempRight = mid+1;
    // 循环遍历判断逆序对
    while(tempLeft <= mid && tempRight <= right){
        // 若左子数组的值较小，则无逆序对，左子数组指针后移，跳过
        if(array[tempLeft] <= array[tempRight]){
            // 将左子数组当前元素添加到临时数组中，临时数组指针后移
            tempArr[i] = array[tempLeft];
            i++;
            tempLeft++;//左子数组指针后移
        }else{//若左子数组的值较大，则逆序对数量为左子数组剩余元素个数
            // 将右子数组当前元素添加到临时数组中，临时数组指针后移
            tempArr[i] = array[tempRight];
            // 左子数组剩余元素个数 = 左子数组终点位置-当前位置
            count += mid+1 - tempLeft;
            count %= 1000000007;
            i++;
            tempRight++;//右子数组指针后移
        }
    }

    //若左子数组还有元素，全部放入临时数组
    while(tempLeft <= mid)
        tempArr[i++] = array[tempLeft++];
    //若右子数组还有元素，全部放入临时数组
    while(tempRight <= right)
        tempArr[i++] = array[tempRight++];
    //将临时数组中的元素放入原数组的对应位置
    for(int num : tempArr)
        array[start++] = num;
}