排序算法

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

1、冒泡排序

从前往后 两两交换，最大的浮到最后

void bubble_sort(T arr[], int len) {
        int i, j;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1])
                                swap(arr[j], arr[j + 1]);

2、选择排序

找到最小 和位置0换，找到次小，和位置1换

void selection_sort(std::vector<T>& arr) {
        for (int i = 0; i < arr.size() - 1; i++) {
                int min = i;
                for (int j = i + 1; j < arr.size(); j++)
                        if (arr[j] < arr[min])
                                min = j;
                std::swap(arr[i], arr[min]);
        }
}

3、插入排序

一把牌，后面没排序的，一张张换到前面来。

void insertion_sort(int arr[],int len){
        for(int i=1;i<len;i++){
                int key=arr[i];
                int j=i-1;
                while((j>=0) && (key<arr[j])){
                        arr[j+1]=arr[j];
                        j--;
                }
                arr[j+1]=key;
        }
}

4、希尔排序

希尔排序是基于插入排序.

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。D=1时退化成插入排序。

vector<int> sortArray(vector<int>& nums) {
    for ( int D = nums.size() / 2; D > 0; D /= 2 ) {
        for ( int i = D; i < nums.size(); i++ ) {
            int key = nums[i];
            int j = i ;
            for ( ; j >= D && nums[j-D] >key; j -= D ) {
                nums[j] = nums[j-D];
            }
            nums[j] = key;
        }
    }
    return nums;
}

5、归并排序

1和2先排序，3和4排序，1234排序

vector<int> tmp;
void mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) >> 1;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    int i = left, j = mid + 1;
    int cnt = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[cnt++] = nums[i++];
        }
        else {
            tmp[cnt++] = nums[j++];
        }
    }
    while (i <= mid) {
        tmp[cnt++] = nums[i++];
    }
    while (j <= right) {
        tmp[cnt++] = nums[j++];
    }
    for (int i = 0; i < right - left + 1; ++i) {
        nums[i + left] = tmp[i];
    }
}

6、堆排序

void maxHeapify(vector<int>& nums, int i, int end) { // 和子比 大子往上 一步步循环往下
    for ( ; i * 2 + 1 <= end; ) {
        int leftSon = 2 * i + 1;
        int rightSon = 2 * i + 2;
        int large = i;
        if ( leftSon <= end && nums[leftSon] > nums[i] ) large = leftSon;
        if ( rightSon <= end && nums[rightSon] > nums[large] ) large = rightSon;
        
        if ( large != i ) {
            swap( nums[i], nums[large] );
            i = large;
        } else break;
    }
}

void heapSort(vector<int>& nums, int len) {
    for ( int i = (len - 1) / 2 ; i >= 0; i-- ) // 从最后一个父节点（独生子也行）开始往回
        maxHeapify(nums, i, len - 1); // 最大值在最上
    
    for ( int i = len - 1; i >= 1; i-- ) {
        swap( nums[i], nums[0] );
        len -= 1;
        maxHeapify(nums, 0, len - 1);
    }
}

7、快速排序

vector<int> sortArray(vector<int>& nums) {
    quickSort( nums, 0, nums.size() - 1 );
    return nums;
}
void quickSort(vector<int>& nums, int left, int right) {
    if ( left < right ) {
        int randVal = rand() % ( right - left + 1 ) + left;
        swap( nums[randVal], nums[right] );

        int pivot = nums[right];
        int i = left - 1;
        for ( int j = left; j < right; j++ ) {
            if ( nums[j] < pivot ) { //j遇小则换
                i = i + 1;
                swap( nums[j], nums[i] );
            }
        }
        swap( nums[right], nums[i+1] );
        int pos = i + 1;

        quickSort(nums, left, pos - 1);
        quickSort(nums, pos + 1, right);
    }
}