前端排序算法 -- 快速排序和归并排序

快速排序算法

1. 介绍

快速排序是一种高效的排序算法，它的核心思想是通过选取一个基准元素，将待排序数组分割成两部分，使得左边的元素都小于等于基准，右边的元素都大于等于基准，然后对左右两部分分别进行递归排序，最终完成整个数组的排序。

2. 实现过程

• 选择一个基准元素。
• 将数组划分成两部分，使得左边的元素都小于等于基准，右边的元素都大于等于基准。
• 对左右两个子数组分别进行递归调用快速排序。
• 合并左右两个子数组，得到最终的排序结果。

3. 伪代码

function quickSort(arr, left, right):
    if left < right:
        pivotIndex = partition(arr, left, right)
        quickSort(arr, left, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, right)

function partition(arr, left, right):
    pivot = arr[left]  // 选择第一个元素作为基准
    i = left + 1
    j = right
    while i <= j:
        while i <= j and arr[i] < pivot:
            i = i + 1
        while i <= j and arr[j] > pivot:
            j = j - 1
        if i <= j:
            swap(arr, i, j)
            i = i + 1
            j = j - 1
    swap(arr, left, j)
    return j

function swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

4. ts实现

function quickSort(arr: number[]): number[] {
    if (arr.length <= 1) {
        return arr;
    }
    
    const pivotIndex = Math.floor(arr.length / 2);
    const pivot = arr.splice(pivotIndex, 1)[0];
    const left: number[] = [];
    const right: number[] = [];
    
    for (const num of arr) {
        if (num < pivot) {
            left.push(num);
        } else {
            right.push(num);
        }
    }
    
    return [...quickSort(left), pivot, ...quickSort(right)];
}

5. c实现

#include <stdio.h>
void swap(int* a, int* b);

int partition(int arr[], int left, int right);

void quickSort(int arr[], int left, int right);

void quickSort(int arr[], int left, int right) {
  if (left >= right) {
    return;
  }

  int pivotIndex = partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);
}

int partition(int arr[], int left, int right) {
  int pivot = arr[left];
  int i = left + 1;
  int j = right;

  while (i <= j) {
    while (i <= j && arr[i] < pivot) {
      i++;
    }
    while (i <= j && arr[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swap(&arr[i], &arr[j]);
      i++;
      j--;
    }
  }

  swap(&arr[left], &arr[j]);
  return j;
}

void swap(int* a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

int main() {
  int arr[] = {5, 2, 9, 3, 7, 6, 1, 4, 8};
  int n = sizeof(arr) / sizeof(arr[0]);

  quickSort(arr, 0, n - 1);

  printf("Sorted array: ");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  return 0;
}

6. 复杂度分析

• 比较复杂度：最坏情况下，快速排序的比较次数为O(n^2)，平均情况下为O(nlogn)。
• 交换复杂度：最坏情况下，快速排序的交换次数为O(n^2)，平均情况下为O(nlogn)。
• 空间复杂度：快速排序的空间复杂度主要取决于递归调用时的栈空间，最坏情况下为O(n)，平均情况下为O(logn)。
• 时间复杂度：最坏情况下，快速排序的时间复杂度为O(n^2)，平均情况下为O(nlogn)。在实际应用中，快速排序通常表现出较好的性能。

归并排序算法

1. 介绍

归并排序是一种稳定的排序算法，其基本思想是将待排序数组递归地分成两个子数组，然后对每个子数组进行排序，并最后合并两个有序子数组以得到最终的排序结果。

2. 实现过程

• 将待排序数组分成两个子数组，直到每个子数组只包含一个元素。
• 对每个子数组进行排序，可以使用递归调用归并排序。
• 合并两个有序子数组，得到一个更大的有序数组。
• 重复上述步骤，直到合并的数组包含所有元素并完成排序

3. 伪代码

function mergeSort(arr):
    if length of arr <= 1:
        return arr
    mid = length of arr / 2
    left = mergeSort(first half of arr)
    right = mergeSort(second half of arr)
    return merge(left, right)

function merge(left, right):
    result = []
    while left is not empty and right is not empty:
        if first element of left <= first element of right:
            append first element of left to result
            remove first element from left
        else:
            append first element of right to result
            remove first element from right
    append remaining elements of left to result
    append remaining elements of right to result
    return result

4. ts实现

function mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) {
        return arr;
    }
    
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let i = 0;
    let j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }
    
    while (i < left.length) {
        result.push(left[i]);
        i++;
    }
    
    while (j < right.length) {
        result.push(right[j]);
        j++;
    }
    
    return result;
}

5. c实现

#include <stdio.h>

void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
    int i = 0, j = 0, k = 0;

    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < leftSize) {
        arr[k] = left[i];
        i++;
        k++;
    }

    while (j < rightSize) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int size) {
    if (size <= 1) {
        return;
    }

    int mid = size / 2;
    int left[mid];
    int right[size - mid];

    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }

    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }

    mergeSort(left, mid);
    mergeSort(right, size - mid);
    merge(arr, left, mid, right, size - mid);
}

int main() {
    int arr[] = {5, 2, 9, 3, 7, 6, 1, 4, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, n);

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

6. 复杂度分析

• 比较复杂度：归并排序的比较次数为O(nlogn)，其中n是待排序数组的大小。
• 交换复杂度：归并排序不涉及元素的直接交换，因此交换次数为0。
• 空间复杂度：归并排序需要额外的存储空间来保存临时数组，在合并过程中需要使用与原始数组相同大小的额外空间，因此空间复杂度为O(n)。
• 时间复杂度：归并排序的时间复杂度为O(nlogn)，这是由于每一层递归都需要对整个数组进行一次遍历，并且递归的深度为logn。