经典排序-思想解析

阐述每种排序方法的思想与复杂度。假设数组大小为$n$，且从小到大排列。

冒泡排序

每一趟排序：两两元素进行比较并交换位置，核心代码如下

if (a[i] > a[i+1]){
    tmp = a[i];
    a[i] = a[i+1];
    a[i+1] = tmp;
}

1. 每一趟排序后，较大的数都被安排到了正确的位置。故只需n-1次排序即可排序完成
2. 存在的问题是：假设在一堂排序后数组已为有序，则不需要后面的遍历与比较了。故优化的方法是，设置一个标志变量来判断数组是否已经有序了。

• 时间复杂度：$Average：O(n^{2})$，$Worst: O(n^{2})$
• 空间复杂度：$O(1)$
• 适用于$n$较小的数组
• 稳定的排序方法

插入排序

以第一个元素为首个基准，从下标1开始的每个元素寻找其插入位置，一躺排序：

for(int i = 1; i < arr.length(); i++){
    int insertVal = arr[i];   // 记录待插入的元素
    int insertIndex = i - 1;
    while(insertIndex >= 0 && arr[insertIndex] > insertVal){
        arr[insertIndex+1] = arr[insertIndex];   // 较大的元素向后移动
        insertIndex--;
    }

    if(insertIndex + 1 != i){   // 发生了移动才交换
        arr[insertIndex + 1] = insertVal; 
    }
}

1. 减少交换元素的操作，转而记录元素的正确位置

• 时间复杂度：$Average：O(n^{2})$

希尔排序

也成缩小增量排序，对每个增量序列：arr[i]..a[i+delta]..a[i+2*delta]..进行插入排序，增量delta持续减小至1：

for(int i = delta; i < arr.length(); i++){  // 从第dk个元素开始
    int insertVal = arr[i];   // 记录待插入的元素
    int insertIndex = i - delta;
    while(insertIndex >= 0 && arr[insertIndex] > insertVal){
        arr[insertIndex + delta] = arr[insertIndex];   // 下标差变为delta
        insertIndex -= delta;
    }

    if(insertIndex + delta != i){   // 发生了移动才交换
        arr[insertIndex + delta] = insertVal; 
    }
}
// 增量序列，数组大小为n
while(n != 1){
    delta = n / 2;
    n = n / 2;
}

1. 对增量序列进行插入排序
2. 效率比插入排序要好

快速排序

递归进行的排序，定义一个轴，使在数组中轴的一部分比轴小，另一部分比轴大:

// 一趟排序如下
int pivot = arr[l];
int low = l;
int high = r;
while(low < high){
    while(low < high && arr[high] >= pivot){
        high--;
    }
    arr[low] = arr[high];  // 找到了比轴小的数，移向low端，接着转而从low开始
    while(low < high && arr[low] < pivot){
        low++;
    }
    arr[high] = arr[low]; // 找到了比轴大的数，移向high端
}
arr[low] = pivot;   // 将轴归位

1. 速度很快。但会利用到递归过程中的栈空间
2. 时间复杂度：$O(n\log_{2}n)$

归并排序

采用了分而治之的思想，并利用了递归。需要一个临时数组存储有序序列，再将其拷贝至原数组。

分过程：不断把数组划分为左右两个子数组

divide(arr, tmp, l, r){
    if(l < r){
        mid = (l + r) / 2;
        divide(arr, tmp, l, mid);  // 左部分
        divide(arr, tmp, mid+1, r);  // 右部分
        merge(arr, tmp, l, mid+1, r) // 合并
    }
}

合过程：将两个有序数组合并

merge(arr, tmp, i, j, r){
    int k = l;
    int left = i;
    int mid = j - 1;
    // 逐个选取两个数组中最小的数放进tmp中
    while(i <= mid && j <= r){
        if(arr[i] < arr[j]){
            tmp[k++] = arr[i++];
        }else{
            tmp[k++] = arr[j++]
        }
    }
    // 放入某个数组剩余的部分
    while(i <= mid){
        tmp[k++] = arr[i++];
    }
    while(j <= r){
        tmp[k++] = arr[j++];
    }
    // 将有序数组重新放回到原数组中
    int left2 = left;
    while(left <= r){
        arr[left++] = tmp[left2++]; 
    }
}

1. 利用到了递归的栈空间
2. 时间复杂度与栈的深度有关。一般为$O(n\log_{2}n)$

堆排序

堆的概念

对于数组$a[n]$:

$$大顶堆 \left\{\begin{matrix} a[i] >= a[2i]\\ a[i] >= a[2i+1] \end{matrix}\right. 或小顶堆 \left\{\begin{matrix} a[i] <= a[2i]\\ a[i] <= a[2i+1] \end{matrix}\right.$$

类比二叉树的概念：根的值大于或小于左右子树的值

利用堆进行排序

两个关键过程：

• 将指定节点下的数调整为一个堆：从最后一个非终端节点$\left \lfloor \frac{n}{2} \right \rfloor$倒序一个个调整，调整其及子树

  adjustHeap(arr, i, n){
      int v = arr[i];
      if(2*i <= n && arr[i] > arr[2*i]){
          arr[i] = arr[2*i];
          arr[2*i] = v;
          adjustHeap(arr, 2*i, n);  // 递归调整下一个节点
      }
      v = arr[i];
      if(2*i+1 <= n && arr[i] > arr[2*i+1]){
          arr[i] = arr[2*i+1];
          arr[2*i+1] = v;
          adjustHeap(arr, 2*i+1)   // 递归调整下一个节点
      }
  }

• 获取堆顶的元素后调整：将最后一个元素放到根$0$的位置上，调整该节点以及子树

  heapSort(arr){
      调整初始数组为一个堆
      for(i = 0; i < n; i++){
          int v = arr[1];
          arr[1] = arr[n-i];
          arr[n-i] = v;   // 最小的数在后面：结果为从大到小
          adjustHeap(arr, 0, n-i-1);  // n-i-1: 堆大小减1
      }
  }

  1. 堆排序适用于n较大的数组
  2. 时间主要用在初始堆的建立过程中