date: 2024-02-28
title: Sort
author:
  - AllenYGY
status: DONE
tags:
  - NOTE
  - Sort
  - Algorithm
created: 2023-12-31
updated: 2024-04-09T11:28
publish: True

Sort Algorithm

Bubble Sort
Insertion Sort
Merge Sort
Quick Sort
Heap Sort

稳定排序：排序前后两个相等的数相对位置不变，则算法稳定
Bubble sort, Insertion sort, Merge sort
非稳定排序：排序前后两个相等的数相对位置发生了变化，则算法不稳定
Quick sort, Heap sort

Default order from smallest to largest

Bubble Sort

Final不考先不写

  public static void sort(int nums[]){
    Bubble(nums, nums.length-1);
  }

  //* 优化 每次循环的最后一次交换后   该下标往右都不会再发生交换 */
  public static void Bubble(int nums[],int j){    
    if(j==0) return ;
    int x=0;
    for(int i=0;i<j;i++){
      if(nums[i]>nums[i+1]) {
        int temp=nums[i];
        nums[i]=nums[i+1];
        nums[i+1]=temp;
        x=i;
      }
    }
    Bubble(nums, x);
  }

Insertion Sort

遍历第一个元素到数组最后一个元素
每遍历一个元素就比较已经排好序的部分，倒序遍历回去知道找到可以插入的位置
Example:
1. 654321
2. 564321
3. 456321
4. 345621
5. 234561
6. 123456

❌ Error: Expected an atom of EOF but received ordinary at position 8: ` A[i+1]↱ = key`

Non-Recursion

public static void insertionSort(int A[]){
  for(int p=1;i<A.length;p++){
    int key=A[p]; int i=p-1;
    while(i>=0 && A[i]>key){
      A[i+1]=A[i]; //挪位置
      i=i-1;
    }
    A[i+1]=key;
  }
}

Recursion

不断缩小排序范围

public static void insertionSort(int A[]){
    Insertion(A, 1);
  }
public static void insertionSort(int A[],int p){
  if(p==A.length) return;
  int key=A[p]; int i=p-1;
  while(i>=0 && key<A[i]){
    A[i+1]=A[i];
    i--;
  }
  A[i+1]=key;
  Insertion(A, p+1);
}

Time Complexity for Insertion Sort

Best-Case: 已经排好序的数组，扫一遍
Worst-Case: 倒序的数组
Average-Case:

Merge Sort

重点讲下merge的过程
- 对于两个有序数组第一个元素下标分别为 $，$

❌ Error: Expected an atom of EOF but received ordinary at position 3: `11.↱ Copy B to A[l`

Time Complexity for Merge Sort

Quick Sort

❌ Error: Expected an atom of EOF but received ordinary at position 3: `15.↱ swap A[i] a`

Strategy for pick pivot

Strategy I

Use the first element as a pivot

if the input is random, ok
if the input is presorted (or in reverse order)
- all the elements go into S2 (or S1)
- this happens consistently throughout the recursive calls
  Results in behavior

Strategy II

Choose the pivot randomly

generally safe
random number generation can be expensive

Strategy III

Use the median of the array 中位数
The median is the middle element if the array is sorted.

Partitioning always cuts the array into roughly half
An optimal quicksort: O(N log N)
However, it is expensive to find the exact median
e.g., sort an array to pick the value in the middle

Strategy IV

We will use the median of three
Compare just three elements: the left-most, right-most, and center

Swap these elements if necessary so that

A[left] = Smallest
A[right] = Largest
A[center] = Median of three
Pick A[center] as the pivot
Swap A[center] and A[right – 1] so that the pivot is at second-last position

Time Complexity for Quick Sort

Assumptions
Pivot Selection: Median of 3
Base Case: Array size <= 10
Running time
- Divide
  1. Pivot selection: O(1)
  2. Partitioning: O(n)
  3. Recursive calls: T(i) + T(n-i-1)
- Conquer and Combine: O(1)

Worst-Case
- The pivot is the smallest element, all the time
- Partition is always unbalanced

Best-Case
- Partition is perfectly balanced
- Pivot is always in the middle (median of the array)

Average-Case

Why is quicksort faster than mergesort?

The inner loop consists of an increment/decrement (by 1, which is fast), a test, and , a jump.
There is no extra juggling as in mergesort.

Heap Sort

Priority Queue

The priority queue is a data structure that allows at least two operations

insert
delete in/deleteMax
- finds, returns, and removes the minimum elements in the priority queue

Binary Heap

Heaps are “almost perfect binary trees”

All levels are full except possibly the lowest level
If the lowest level is not full, then nodes must be packed to the left

Property

Given a binary heap of node number n and height h

n is within
The height
The structure is so regular, it can be represented in an array and no links are necessary !!!

Insert in time
Locate the current minimum in time
Delete the current minimum in time

❌ Error: Expected an atom of EOF but received ordinary at position 2: `9.↱ return Tr`

Note:
节点A：
父节点：

❌ Error: Expected an atom of EOF but received ordinary at position 3: `11.↱ return min`

❌ Error: Expected an atom of EOF but received ordinary at position 2: `5.↱ A[i] `