乐趣区

关于java:知识总结排序

jiezi

不具备稳定性的排序：抉择排序、疾速排序、堆排序

具备稳定性的排序：冒泡排序、插入排序、归并排序（nlogn）

抉择排序

每次遍历找到数组中最小的元素的索引，顺次替换。

public int[] sortArray (int[] nums) {for(int i=0; i<nums.length; i++) {
        int minIndex = i;
        for(int j=i+1; j<nums.length; j++) {minIndex = nums[j] < nums[minIndex] ? j : minIndex; 
        }
        swap(nums, i, minIndex);
    }
    return nums;
}

疾速排序

  • 疾速排序是由上到下的，先分区，而后再解决子问题。

基本思路：

  1. 先从数组中找一个基准数
  2. 让其余比它大的元素挪动到数组一边，比他小的元素挪动到数组另一边。从而把数组拆解成两局部。
  3. 再对左右区间反复第二部，直到各区间只有一个数。

low 指针找到大于 pivot 的元素，hight 指针找到小于 pivot 的元素，而后两个元素替换地位，最初再将基准数归位。

  • 填坑法
public void quickSort (int[] nums, int low, int high) {if(low < high) {int index = partition(nums, low, high);
        quickSort(nums, low, index-1);
        quickSort(nums, index+1, high);
    }
}

public int partition(int[] nums, int low, int high) {int pivot = nums[low];

    while(low < high) {while(low<high && nums[high] >= pivot) {high--;}
        nums[low] = nums[high];
        while(low<high && nums[low] <= pivot) {low++;}
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    return low;
}
  • 交换法

其实这种办法，算是对下面办法的挖坑填坑步骤进行合并，low 指针找到大于 pivot 的元素，hight 指针找到小于 pivot 的元素，而后两个元素替换地位，最初再将基准数归位。

public void quickSort (int[] nums, int low, int high) {if(low < high) {int index = partition(nums, low, high);
        quickSort(nums, low, index-1);
        quickSort(nums, index+1, high);
    }
}

public int partition(int[] nums, int low, int high) {int pivot = nums[low];
    int start = low;    // 记录 low 指针

    while(low < high) {while(low < high && nums[high] >= pivot)  high--;
        while(low < high && nums[low] <= pivot)    low++;

        if(low >= high) {break;}
              
        swap(nums, low, high); 
    }
    // 基准值归位
    swap(nums, start, low);
    return low;
}

    public void swap(int[] nums, int i, int j) {if(i == j) return;
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }

冒泡排序

两两比拟相邻记录的关键字，如果是反序则替换，直到没有反序为止。

public int[] sortArray(int[] nums) {for(int i=0; i<nums.length; i++) {for(int j=0; j<nums.length-i-1; j++) {if(nums[j] > nums[j+1]) {swap(nums, j, j+1);
            }
        }
    }
    return nums;
}


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

冒泡排序能够用 标识 flag 改良，如果替换则标识位发生变化，如果标识为没有变动，阐明曾经排序好了！

插入排序

一直地与后面的数字比拟，如果后面的数字比它大，它就和后面的数字替换地位。

public int[] sortArray(int[] nums) {for(int i=1; i<nums.length; i++) {
        int j = i;  // 记录以后数字下标

        // 以后数字比前一个数字小，则替换
        while(j >= 1 && nums[j] < nums[j-1]) {swap(nums, j, j-1);

            j--;  // 持续向前一个元素比拟
        }
    }
    return nums;
}

public void swap(int[] nums, int i, int j) {int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

归并排序

  • 归并排序采纳的是 分治法 思维。
  • 整体就是简略的递归，右边排好序，左边排好序，再让其整体有序。怎么整体有序呢？筹备一个辅助空间，看看两边排好序的右边，比拟谁小就谁先进入这个辅助空间（外排序办法）
  • 归并排序中的 比拟次数 是所有排序中 起码 的，它一开始是一直地划分，比拟只产生在合并各个有序的子数组时。

public int[] sortArray (int[] nums) {int[] temp = new int[nums.length];   
    mergeSort(nums, 0, nums.length-1, temp);
    return nums;     
}

public void mergeSort(int[] nums, int low, int high, int[] temp) {int mid = (low + high) / 2;
    if(low < high) {
        // 对左右进行拆分
        mergeSort(nums, low, mid, temp);
        mergeSort(nums, mid+1, high, temp);
        // 合并
        merg(nums, low, high, mid, temp);
    }
}

public void merg(int[] nums, int low, int high, int mid, int[] temp) {
    int index = 0;
    int i = low;        // 右边序列起始索引
    int j = mid + 1;    // 左边序列起始索引
        
    while(i <= mid && j <= high) {if(nums[i] <= nums[j]) {            // 这里最好用 <=
            temp[index++] = nums[i++];
        } else {temp[index++] = nums[j++];
        }
    }

    // 若右边序列还有残余
    while(i <= mid) {temp[index++] = nums[i++];
    }

    // 若左边序列还有残余
    while(j <= high) {temp[index++] = nums[j++];
    }

    // 把 temp 数组的赋值给原数组 nums
    for(int t=0; t<index; t++) {nums[low + t] = temp[t];
    }
}

工夫复杂度为：O(NlogN)

额定空间复杂度为：O(N)

堆排序

  • 二叉堆，必须是齐全二叉树，而且二叉堆中的每一个节点，都必须大于等于（或小于等于）其子树中每个节点的值。

  • 因为堆是齐全二叉树，所以咱们齐全能够用 数组存储。将根节点的下标视为 0，则齐全二叉树有如下性质：

    • 它的左子节点下标：2i + 1
    • 它的右子节点下标：2i + 2
    • 对于有 n 个元素的齐全二叉树（n >2），它的最初一个 非叶子结点 的下标：n/2 - 1

构建大顶堆：将整个数列的初始状态视作一棵齐全二叉树，自底向上调整树的构造，使其满足大顶堆的要求。

变量 heapSize 用来记录还剩下多少个数字没有排序实现，每当替换了一个堆顶的数字，heapSize 就会减 1。在 maxHeapify 办法中，应用 heapSize 来限度剩下的选手，不要和曾经躺在数组最初，当过冠军的人比拟，省得被暴揍。

  1. 构建初始大顶堆，从最初一个非叶子节点开始堆化。
  2. 进入循环，将最大值放到数组的最初，并且堆化调整地位。循环最大索引次，排序结束。
public int[] sortArray(int[] nums) {
    // 构建初始大顶堆
    buildMaxHeap(nums);

    for(int i=nums.length - 1; i >= 0; i--) {swap(nums, 0, i);   // 将最大值放到数组的最初
        maxHeapify(nums, 0, i); // 调整残余数组，使其满足大顶堆
    }
    return nums;
}


public void buildMaxHeap(int[] nums) {
    // 从最初一个非叶子结点开始调整大顶堆，最初一个非叶子结点的下标就是 arr.length / 2-1
    for(int i = nums.length / 2 - 1; i>=0; i--) {maxHeapify(nums, i, nums.length);
    }
}

// 调整大顶堆（第三个参数示意残余未排序的数字的数量，也就是残余堆的大小）public void maxHeapify(int[] nums, int i, int heapSize) {
    int l = 2 * i + 1;      // 左子结点下标
    int r = l + 1;          // 右子结点下标

    int largest = i;        // 记录根结点和两个儿子之间的最大值

    if(l < heapSize && nums[l] > nums[largest])  largest = l;
    if(r < heapSize && nums[r] > nums[largest])  largest = r;

    // 如果有子结点大于根结点，则替换，并用 largest 去再次调整大顶堆。if(largest != i) {swap(nums, i, largest);
        maxHeapify(nums, largest, heapSize);
    }
}

public void swap(int[] nums, int i, int j) {int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
退出移动版