[数据结构与算法]Day1：排序算法（上）

一、插入排序

1. 直接插入排序

若已有一个有序序列，那么将新的元素插入到它的有序位置上，就可以形成新的有序序列。
根据上述思想，可以将单个元素的序列设为初始的有序子序列，每次将下一元素插入到该子序列中，形成规模（长度）+1的子序列。直至将所有元素都插入完成，原序列成为有序序列。

void InsertSort(int nums[], int n)
{
	int j;
    for(int i = 1;i < n;i++) {          // 将第i + 1个元素插入到前i有序序列中的正确位置
        if(nums[i] < nums[i - 1]) {     // else下插入位置在序列尾，无需找插入位置
            int num = nums[i];          // 记录待排元素
            for(j = i - 1;j >= 0 && num < nums[j];j--) {    // 找插入位置
                nums[j + 1] = nums[j];  // 元素后移
            }
            nums[j + 1] = num;          // 插入
        }
    }
}

时间复杂度：O( n²)
空间复杂度：O(1)
稳定性：稳定

2. 二分插入排序

与直接插入类似，但将查找插入位置的过程由简单的顺序查找替换为二分查找。

void BiInsertSort(int nums[], int n)
{
	for(int i = 1;i < n;i++) {          // 将第i + 1个元素插入到前i有序序列中的正确位置
        int num = nums[i], low = 0, high = i - 1;   // 二分查找的上下界
        while(low <= high) {            // 二分查找
            int mid = (low + high) / 2;
            if(nums[mid] > num) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }   // 查找结束时，high + 1为正确插入位置
        for(int j = i - 1;j >= high + 1;j--) {  // 后移
            nums[j + 1] = nums[j];
        }
        nums[high + 1] = num;
    }
}

时间复杂度：O(n²) 仅能减少查找次数，不能减少移动次数
空间复杂度：O(1)
稳定性：稳定

3. 希尔排序

直接插入排序的性能与初始序列的有序性相关。初始序列基本有序，则直接插入排序具有较好的性能。
基于这一情况，希尔排序每次基于一个逐渐缩小增量对多个子序列进行排序，以求序列逐渐趋于有序化。最后通过一次增量为1的比较完成排序。

void ShellSort(int nums[], int n)
{
	for(int dk = n /2;dk >= 1;dk /= 2) {       // 初始增量设为n/2，每次缩短一半
        for(int i = dk;i < n;i++){      // 对增量子序列作插入排序
            if(nums[i] < nums[i - dk]) {
                int num = nums[i];
                int j;
                for(j = i - dk;j >= 0 && num < nums[j];j -= dk){
                    nums[j + dk] = nums[j];
                }
                nums[j + dk] = num;
            }
        }
     }
}

时间复杂度：O(n^1.3) ~ O(n²)，介于O(nlog n)和O(n²)的排序算法之间
空间复杂度：O(1)
稳定性：不稳定

二、交换排序

1. 冒泡排序

通过相邻元素的比较和交换，将一个最大（或最小）的元素移动到最终位置上。

void BubbleSort(int nums[], int n)
{
	for(int i = 0;i < n - 1;i++) {
        int flag = 0;       // 发生交换标志，可用于提前结束
        for(int j = n - 1;j > i;j--) {      // 单趟冒泡
            if(nums[j - 1] > nums[j]){
                Swap(&nums[j-1], &nums[j]);
                flag = 1;
            }
        }
        if(flag == 0) {     // 一趟冒泡未发生交换，已经有序
            return;
        }
     }
}

// 补充Swap函数
 void Swap(int *a, int *b)
 {
     int temp = *a;
     *a = *b;
     *b = temp;
 }

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

2. 快速排序

基于分治法的思想，先选取一个枢轴并将其移动到最终位置上，枢轴之前的数据均小于（不大于）枢轴的值，之后的数据均大于（不小于）枢轴的值，再对两边递归调用快速排序的划分。

 void QuickSort(int nums[], int n)		// 启动
 {
     QuickSortRec(nums, 0, n - 1);
 }

 void QuickSortRec(int nums[], int low, int high)	// 递归快排
 {
     if(low < high) {
        int pivot = Partition(nums, low, high);       // 此处pivot与划分中不同，为枢轴所在下标
        QuickSortRec(nums, low, pivot - 1);
        QuickSortRec(nums, pivot + 1, high);
     }
 }
 
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];     // 找到左侧大元素，移至右侧
    }   // while结束时，一定是low == high，此位置为枢轴的最终位置
    nums[low] = pivot;
    return low;
 }

时间复杂度：O(n·log n)
空间复杂度：O(n·log n) 递归调用时的栈空间
稳定性：不稳定