常见排序算法

【道德经·第五章】天地不仁，以万物为刍（chú）狗；圣人不仁，以百姓为刍狗。天地之间，其犹橐龠（tuó yuè）乎？虚而不屈，动而愈出。多言数（shuò）穷，不如守中。

插入排序

插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成。
由插入排序的的思想可以引申出三个重要的排序算法：直接插入排序、折半插入排序和希尔排序。下面依次进行介绍~

直接插入排序

void InserSort(int nums[], int n) {
    int i, j;
    for(i = 2; i <= n; i++) {
        if(nums[i] < nums[i-1]) {
            nums[0] = nums[i];  // nums[0]哨兵，不存放元素
            for(j = i-1; nums[0] < nums[j]; --j)
                nums[j+1] = nums[j];
            nums[j+1] = nums[0];  // 复制nums[0]到插入位置
        }
    }
}

时间复杂度：最好情况O(n)，最坏情况O(n²)；空间复杂度: O(1)； 稳定性：由于每次插入元素时总是从后往前先比较再移动，所以不会出现相等元素相对位置发生变化的情况，即直接插入排序是一种稳定的排序方法

折半插入排序

void InsertSort(int nums[], int n) {
    int i, j;
    int low, high, mid;
    for(i = 2; i <= n; i++) {
        nums[0] = nums[i];
        low = 1;
        high = i-1;
        while(low <= high) {
            mid = (low + high) / 2;
            if(nums[0] < nums[mid]) high = mid-1;
            else low = mid+1;
        }
        for(j = i-1; j >= high+1; --j)
            nums[j+1] = nums[j];
        nums[high+1] = nums[0];
    }
}

时间复杂度：折半插入排序仅减少了比较元素的次数，而元素的移动次数并未改变，因此时间复杂度仍为O(n²)；空间复杂度: O(1)；稳定性：稳定

希尔排序

void ShellSort(int nums[], int n) {
    for(dk = n/2; dk >= 1; dk = dk/2) {
        for(i = dk+1; i <= n; i++) {
            if(nums[i] < nums[i-dk]) {
                nums[0] = nums[i];
                for(j = i-dk; j>0 && nums[0]<nums[j]; j -= dk)
                    nums[j+dk] = nums[j];
                nums[j+dk] = nums[0];
            }
        }
    }
}

时间复杂度：n在某个特定范围内时，希尔排序时间复杂度为O(n^1.3)，最坏情况下复杂度为O(n²)；空间复杂度: O(1)；稳定性：不稳定

交换排序

所谓交换，就是指根据序列中两个元素的比较结果来对换这两个记录在序列中的位置。交换排序的算法很多，本文主要介绍冒泡排序和快速排序。

冒泡排序

void BubbleSort(int nums[], int n) {
    for(int i = 0; i < n-1; i++) {
        bool flag = false;
        for(int j = n-1; j > i; j--) {
            if(nums[j-1] > nums[j]) {
                swap(nums[j-1], nums[j]);
                flag = true;
            }
        }
        if(flag == false) return;  // 本趟没有发生交换，说明序列已经有序
    }
}

时间复杂度: 最好情况下为O(n)，最坏情况下O(n²)；空间复杂度: O(1)；稳定性：稳定

快速排序

快速排序是对冒泡排序的一种改进，其基本思想是基于分治法。在待排序表L[1…n]中任取一个元素pivot作为基准，通过一趟排序算法将待排序表划分为独立的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素小于pivot，L[k+1…n]中的所有元素大于等于pivot，则pivot放在了其最终位置L[k]上，这个过程称为一趟快速排序。而后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素都放在了其最终位置上。

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;  // 返回最终位置
}

// partitionII
int partition(vector<int>& nums, int l, int r) {
    // 随机数选枢轴
    int randIdx = l + rand() % (r - l + 1);
    swap(nums[r], nums[randIdx]);
    
    int pivot = nums[r];
    
    int i = l;
    for(int j = l; j < r; j++) {
        if(nums[j] < pivot) {
            swap(nums[i], nums[j]);
            i += 1;
        }
    }
    
    swap(nums[i], nums[r]);
    return i;
}

void QuickSort(int nums[], int low, int high) {
    if(low < high) {
        int pivotpos = Partition(nums, low, high);
        QuickSort(nums, low, pivotpos-1);
        QuickSort(nums, pivotpos+1, high);
    }
}

时间复杂度: 最好情况下为O(nlogn)，最坏情况下O(n²)；空间复杂度: 最好情况下为(logn)，最坏情况下O(n)；稳定性：不稳定

选择排序

选择排序基本思想是：每一趟在后面n-i+1个待排序元素中选择关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个。选择排序中的堆排序是考察的重点。

简单选择排序

void SelectSort(int nums[], int n) {
    int i;
    for(i = 0; i < n-1; i++) {
        int min = i;
        for(int j = i+1; j < n; j++) {
            if(nums[j] < nums[i]) 
                min = j;
        }
        if(min != i) swap(nums[i], nums[min])
    }
}

堆排序

建立大根堆的算法

void BuildMaxHeap(int nums[], int len) {
    for(int i = len/2; i > 0; i--) {
        AdjustDown(nums, i, len);  // 从i=[n/2]~1，反复调整堆
    }
}

下面是堆向下调整算法

void AdjustDown(int nums[], int k, int len) {
    nums[0] = nums[k];
    for(int i = 2*k; i <= len; i *= 2) {  // 沿k较大的子节点向下筛选
        if(i<len && nums[i]<nums[i+1])
            i++;                          // 取k较大的子节点的下标
        if(nums[0]>=nums[i]) break;       // 筛选结束
        else {
            nums[k] = nums[i];            // 将nums[i]调整到双亲节点上
            k = i;                        // 修改k值，以便继续向下筛选
        }
    }
    nums[k] = nums[0];                     // 被筛选节点的值放入最终位置
}

下面是堆排序算法

void HeapSort(int nums[], int len) {
    BuildMaxHeap(nums, len);              // 初始建堆
    for(int i = len; i > 1; i--) {            
        swap(nums[i], nums[1]);           // 输出堆顶元素（和堆底元素交换）
        AdjustDown(nums, 1, i-1);         // 整理，把剩下的i-1个元素整理成堆
    } 
}

对堆进行插入操作时，先将新节点放在堆的末端，再对这个新节点执行向上调整操作。
下面是堆的向上调整算法

void AdjustUp(int nums[], inr k) {
// 参数k为向上调整的节点，也为堆的元素个数
    nums[0] = nums[k];
    int i = k/2;
    while(i>0 && nums[i]<nums[0]) {
        nums[k] = nums[i];
        k = i;
        i = i/2;
    }
    nums[k] = nums[0];
}

时间复杂度: 建堆时间复杂度O(n)，每次调整时间复杂度O(h)，故在最好、最坏和平均情况下堆排序时间复杂度为O(nlogn)；空间复杂度: O(1)；稳定性：不稳定

归并排序

递归形式的2路归并排序算法是基于分治的其过程如下：
分解：将含有n个元素的待排序表分成含n/2个元素的子表，采用2路归并排序算法对两个子表递归地进行排序。
合并：合并两个已经排序的子表得到排序结果。

void MergeSort(int nums[], int low, int high) {
    if(low < high) {
        int mid = (low + high) / 2;       
        MergeSort(nums, low, mid);
        MergeSort(nums, mid+1, high);
        Merge(nums, low, mid, high);
    }
}

int *_copy = (int*)malloc((n+1)*sizeof(int));
void Merge(int nums, int low, int mid, int high) {
    for(int k = low; k <= high; k++) 
        _copy[k] = nums[k];
    int i,j;
    for(i=low, j=mid+1, k=i; i<=mid && j<=high; k++) {
        if(_copy[i] <= _copy[j])
            nums[k] = _copy[i++];
        else
            nums[k] = _copy[j++];
    }
    while(i <= mid) nums[k++] = _copy[i++];
    while(j <= high) nums[k++] = _copy[j++];
}

时间复杂度: 每趟归并时间复杂度为O(n)，共需logn趟归并，所以算法时间复杂度为O(nlogn)；空间复杂度: 辅助空间占用n个单元，故空间复杂度为O(n)；稳定性：稳定

位我上者，灿烂星空；道德律令，在我心中。