交换排序

1. 冒泡排序

• 时间复杂度O(n²)
• 空间复杂度O(1)
• 稳定
• 适用：顺序存储和链式存储的线性表

n个元素，n-1趟排序，每趟把最大的排到最后。

int i, j;
int flag;
for (i = 0; i < n - 1; i++) {
    
    flag = 0
    for (j = 0; j < n - 1 - i; j++) {
    
        if (L[j] > L[j + 1]) {
    
            int tmp = L[j];
            L[j] = L[j + 1];
            L[j + 1] = tmp;
            flag = 1;
        } 
    }
    if (!flag) break; 
}

2. 快速排序

• 时间复杂度O(nlog₂n),最坏会退化为O(n²)
• 空间复杂度最好O(log₂n)，最坏O(n)
• 不稳定
• 适用：顺序存储的线性表

基于分治，每次排序将确定一个枢轴(基准)pivot

然后将表通过枢轴一分为二，保证左边均小于pivot，右边均大于pivot。

此举将保证pivot已经落在了最终序列的相应位置。

运用递归的思想，将子表重新快速排序。

void quick_sort(ElemType L[], int l, int r) {
    
    if (l < r) {
    
    	int cut = partition(L, l, r);
    	quick_sort(L, l, cut - 1);
    	quick_sort(L, cut + 1, r);
    }
}

快速排序好坏的关键取决于划分算法partition，写法根据枢轴的选择而不同

int partition(ElemType L[], int l, int r) {
    
    ElemType cut = L[l]; 	// 选取最左边元素为枢轴(可不同)
    while (l < r) {
    
        while (l < r && L[r] >= cut) --r;
        L[l] = L[r];
        while (l < r && L[l] <= cut) ++l;
        L[r] = L[l];
    }
    L[l] = cut;
    return l;
}

3. 例

LeetCode 912. 排序数组

// 交换排序
int* sortArray(int* nums, int numsSize, int* returnSize)
{
    
    *returnSize = numsSize;
    int i, j;
    int flag;
    for (i = 0; i < numsSize - 1; i++) {
    
        flag = 0;
        for (j = 0; j < numsSize - 1 - i; j++) {
    
            if (nums[j] > nums[j + 1]) {
    
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                flag = 1;
            }
        }
        if (!flag) return nums;
    }
    return nums;
}

// 快速排序
int partition(int* L, int l, int r) 
{
    
    int cut = L[l]; 	// 选取最左边元素为枢轴(可不同)
    while (l < r) {
    
        while (l < r && L[r] >= cut) --r;
        L[l] = L[r];
        while (l < r && L[l] <= cut) ++l;
        L[r] = L[l];
    }
    L[l] = cut;
    return l;
}

void quick_sort(int* L, int l, int r) 
{
    
    if (l < r) {
    
    	int cut = partition(L, l, r);
    	quick_sort(L, l, cut - 1);
    	quick_sort(L, cut + 1, r);
    }
}

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    
    *returnSize = numsSize;
    quick_sort(nums, 0, numsSize - 1);
    return nums;
}