【1.排序】
排序 笔记记录
- 1.排序的基本概念
- 1.1 排序的定义
- 2. 插入排序
- 2.1 直接插入排序
- 2.2 折半插入排序
- 2.3 希尔排序
- 3. 交换排序
- 3.1 冒泡排序
- 3.2 快速排序
- 4. 选择排序
- 4.1 简单选择排序
- 4.2 堆排序
- 5. 归并排序、基数排序和计数排序
- 5.1 归并排序
- 4.2 基数排序
- 4.3 计数排序
- 6. 各种内部排序算法的比较及应用
- 7. 外部排序
- 8. 一些常见结论
1.排序的基本概念
1.1 排序的定义
- 排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便， 通常希望计算机中的表是按关键字有序的。
- 稳定性：排列后元素的相对位置不发生改变。稳定性不能衡量一个算法的优劣。
- 在排序过程中，根据数据元素是否完全存放在内存中，可将排序算法分为两类：①内部排序， 是指在排序期间元素全部存放在内存中的排序；②外部排序，是指在排序期间元素无法全部同时 存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。
一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。当然，并非所有的内部 排序算法都要基于比较操作，事实上，基数排序就不基于比较操作。
每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性能而言，很难提出 一种被认为是最好的算法。通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序 和基数排序五大类。内部排序算法的性能取决于算法的时间复杂度和空间复杂度，而时间复杂度一般是由比较和移动的次数决定的。
2. 插入排序
插入排序是一种简单直观的排序算法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法：直接插入排序、折半插入排序和希尔排序。
2.1 直接插入排序
- 实现对L[1…n]的排序，可以将L(2)～L(n)依次插入前面已排好序的子序列，初始L[1] 可以视为一个已排好序的子序列。上述操作执行n-1次就能得到一个有序的表。插入排序在实现 上通常采用原地排序(空间复杂度为 O(1),因而在从后往前的比较过程中，需要反复把已排序 元素逐步向后挪位，为新元素提供插入空间。
- 比较次数和移动次数取决于待排序表的初始状态。
- 空间复杂度O(1)
- 时间复杂度：最好O(n) 平均O(n2) 最差O(n2)
- 稳定性：稳定
- 适用性：链式存储和顺序存储都适用，链式存储不用移动元素
static void insertSort(int[] A, int n) {
int j, temp;
//从第二个位置开始判断并插入到前面的有序队列中
for (int i = 1; i < n; i++) {
//如果发现当前的比有序队列还小,就进行插入操作
if (A[i] < A[i - 1]) {
//temp存的是待插入元素
temp = A[i];
//一个个比较直到找到temp的位置，只要temp小于有序元素，就向后移一位 12355
for (j = i - 1; j >= 0 && temp < A[j]; j--) {
A[j + 1] = A[j];
}
//最终的
A[j + 1] = temp;
}
}
}
2.2 折半插入排序
- 从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作：①从前面的有序子 表中查找出待插入元素应该被插入的位置；②给插入位置腾出空间，将待插入元素复制到表中的 插入位置。注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半 查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时， 可以对直接插入排序算法做如下改进：因为是顺序存储的线性表，所以查找有序子表时可以用折 半查找来实现。
- 比较次数与待排序表的初始状态无关。
- 空间复杂度O(1)
- 时间复杂度：最好O(n) 平均O(n2) 最差O(n2)
- 稳定性：稳定
- 适用性：顺序存储
static void halfInsertSort(int[] A, int n) {
int j, temp, low, high, mid;
for (int i = 1; i < n; i++) {
if (A[i] < A[i - 1]) {
temp = A[i];
low = 0;
high = i - 1;
//查找待排元素位置
while (low <= high) {
//这个写法主要是为了避免high特别大的情况，防止溢出 high比low多的分一半给low也就是两人各自一半
mid = low + (high - low) / 2;
if (temp < A[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
//最终high的下一个位置就是待插入位置，这里只需要记住high最终会停在真实位置的前一个位置，所以大于high的都向后移动
for (j = i - 1; j > high; j--) {
A[j + 1] = A[j];
}
//这里high的下一个位置就是temp真正的位置
A[high + 1] = temp;
}
}
}
2.3 希尔排序
从前面的分析可知，直接插入排序算法的时间复杂度为O(n2),但若待排序列为“正序”时， 其时间效率可提高至O(n),由此可见它更适用于基本有序的排序表和数据量不大的排序表。希 排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。
- 希尔排序的基本思想是：先将待排序表分割成若干形如L[i,i+d,i+2d,…,i+kd]的“特殊” 子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个 表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
- 空间复杂度O(1)
- 时间复杂度：最好O(n1.3) 最差O(n2)
- 稳定性：不稳定
- 适用性：顺序存储
public static void shellSort(int[] arr, int n) {
// 初始步长
int gap = n / 2;
// 循环减小增量
while (gap > 0) {
// 对每个组进行直接插入排序 2, 4, 3, 5, 1, 6
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
/**
* 将arr[i]插入到已排序的序列中
* arr[j - gap] > temp这里的意思是步长前元素与步长元素比较如果大于步长元素,
* 则说明不是有序的，将原本的元素放入步长位置
* 且j恢复到原来的位置，继续比较
*/
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
//这里其实就是与最初的元素互换位置
arr[j] = temp;
System.out.println(Arrays.toString(arr));
}
// 减小步长
gap /= 2;
}
}
3. 交换排序
所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。 基于交换的排序算法很多，本书主要介绍冒泡排序和快速排序。
3.1 冒泡排序
冒泡排序的基本思想是：从后往前(或从前往后)两两比较相邻元素的值，若为逆序(即 A[i-1]>A[i]),则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置(或将最大的元素交换到待排序列的最后一个位置),关键字最小 的元素如气泡一般逐渐往上“漂浮”至“水面”(或关键字最大的元素如石头一般下沉至水底)。 下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素(或 最大元素)放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
- 空间复杂度O(1)
- 时间复杂度：最好O(n2) 最差O(n2)
- 稳定性：稳定
- 适用性：顺序存储和链式存储
static void bubbleSort(int[] arr, int n) {
//给个标记 防止在某一趟已经排好序了还继续无用的循环 查看是否有元素交换
boolean flag = false;
for (int i = 0; i < n - 1; i++) {
//这里的n-i-1是因为每一趟都会将最大的元素排到最后，也就是只需要排剩下的n-i-1个元素
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
//进入这个if分支里边，则说明有元素进行了交换
//所以将flag=true
flag = true;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
//在进行完一轮的排序之后，判断本轮是否发生了元素之间的交换
//如果没有发生交换，说明数组已经是有序的了，则直接结束排序
if (!flag) {
break;
} else {
//如果发生了交换，那么在下一轮排序之前将flag再次置为false
//以便记录下一轮排序的时候是否会发生交换
flag = false;
}
}
}
3.2 快速排序
快速排序(以下有时简称快排)的基本思想是基于分治法的：在待排序表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)上，这个过程称为一次划分。然后分 别递归地对两个子表重复上述过程，直至每部分内只有一个元素或为空为止，即所有元素放在了 其最终位置上。
- 快速排序是所有内部排序算法中平均性能最优的排序算法。
- 空间复杂度O(1)
- 时间复杂度：最好O(log2n) 最差O(n2)
- 稳定性：不稳定
- 适用性：快速排序仅适用于顺序存储的线性表。
/**
* 快速排序
*/
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
/**
* 分区操作，找到基准元素的正确位置，并返回该位置
*
* @param arr
* @param low
* @param high
* @return
*/
static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[low] = arr[i];
arr[i] = pivot;
return i;
}
4. 选择排序
选择排序的基本思想是：每一趟(如第i趟)在后面n-i+1(i=1,2,…,n-1)个待排序元 素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只 剩下1个，就不用再选。
4.1 简单选择排序
假设排序表为 L[1.n],第i趟排序即从L[i…n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。
- 空间复杂度O(1)
- 时间复杂度：最好O(n2) 最差O(n2)
- 稳定性：不稳定
- 适用性：简单选择排序适用于顺序存储和链式存储的线性表，以及关键字较少的情况。
static void selectSort(int[] arr, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
4.2 堆排序
堆的定义如下，n个关键字序列L[1…n]称为堆，当且仅当该序列满足：
①L(i)>=L(2i)且L(i)>=L(2i+1)或
② L(i)<=L(2i)且L(i)<=L(2i+1)(1≤i≤Ln/2」)
可以将堆视为一棵完全二叉树，满足条件①的堆称为大根堆(大顶堆),大根堆的最大元素 存放在根结点，且其任意一个非根结点的值小于或等于其双亲结点值。满足条件②的堆称为小根 堆(小顶堆),小根堆的定义刚好相反，根结点是最小元素。
堆排序的思路很简单：首先将存放在L[1-n]中的n个元素建成初始堆，因为堆本身的特点 (以大顶堆为例),所以堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时 根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再 输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。可见，堆排序需要解决两个问题：①如何将无序序列构造成初始堆?②输出堆顶元素后，如何将剩余元素调整成新的堆?
- 空间复杂度O(1)
- 时间复杂度：最好O(nlog2n) 平均O(nlog2n) 最坏O(nlog2n)
- 稳定性：不稳定
- 适用性：适用于顺序存储。
public static void heapSort(int[] arr, int n) {
//初始化堆
for (int i = n / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, n);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
adjustHeap(arr, 0, i);
}
}
public static void adjustHeap(int[] arr, int i, int n) {
while (true) {
int l = 2 * i + 1;
int r = 2 * i + 2;
int index = i;
if (l < n && arr[l] > arr[index]) {
index = l;
}
if (r < n && arr[r] > arr[index]) {
index = r;
}
if (i != index) {
int temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
i = index;
} else {
break;
}
}
}
5. 归并排序、基数排序和计数排序
5.1 归并排序
归并排序与上述基于交换、选择等排序的思想不一样，归并的含义是将两个或两个以上的有 序表合并成一个新的有序表。假定待排序表含有n个记录，则可将其视为n个有序的子表，每个 子表的长度为1,然后两两归并，得到「n/2]个长度为2或1的有序表；继续两两归并……如此重 复，直到合并成一个长度为n的有序表为止，这种排序算法称为二路归并排序。
- 空间复杂度O(n)
- 时间复杂度：O(nlog2n)
- 稳定性：稳定
- 适用性：适用于顺序存储和链式存储。
public static void mergeSort(int[] arr, int left, int right) {
//确保不会越界
if (left < right) {
//从中间划分两个序列
int mid = left + (right - left) / 2;
//左边部分
mergeSort(arr, left, mid);
//右边部分
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
//左边子数组的第一个元素。
int i = left;
//右边子数组的第一个元素
int j = mid + 1;
int k = 0;
//当 i 和 j 都在各自子数组范围内时循环。
while (i <= mid && j <= right) {
//谁小把谁放进temp数组
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
//走到这里说明上面有一个已经放完了所有元素,可能另外一个数组还有元素则继续加入temp数组
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组的结果拷贝回原数组
for (int m = 0; m < temp.length; m++) {
arr[left + m] = temp[m];
}
}
4.2 基数排序
基数排序是一种很特别的排序算法，它不基于比较和移动进行排序，而基于关键字各位的大 小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
- 空间复杂度O®
- 时间复杂度：O(d(n+r))
- 稳定性：稳定
- 适用性：适用于顺序存储和链式存储。
4.3 计数排序
计数排序也是一种不基于比较的排序算法。计数排序的思想是：对每个待排序元素x,统计 小于x的元素个数，利用该信息就可确定x的最终位置。例如，若有8个元素小于x,则x就排 在第9号位置上。当有几个元素相同时，该排序方案还需做一定的优化。
static int[] countSort(int[] arr) {
//1.得到数列的最大值与最小值，并算出差值d
int max = arr[0];
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
int d = max - min;
//2.创建基于差值长度的统计数组并统计填充对应元素个数
int[] countArray = new int[d + 1];
for (int i = 0; i < arr.length; i++) {
countArray[arr[i] - min]++;
}
//3.统计数组变形，后面的元素等于前面的元素之和
for (int i = 1; i < countArray.length; i++) {
countArray[i] = countArray[i] + countArray[i - 1];
}
int[] output = new int[arr.length];
//保证原来元素的顺序 保持稳定
for (int i = arr.length - 1; i >= 0; i--) {
//arr[i] - min真正在countArray中的索引位置
output[countArray[arr[i] - min] - 1] = arr[i];
//避免相同的元素放在同一个位置 应该放在自己对应的位置
countArray[arr[i] - min]--;
}
return output;
}
6. 各种内部排序算法的比较及应用
- 从时间复杂度看：简单选择排序、直接插入排序和冒泡排序平均情况下的时间复杂度都为 O(n2),且实现过程也较为简单，但直接插入排序和冒泡排序最好情况下的时间复杂度可以达到 O(n),而简单选择排序则与序列的初始状态无关。希尔排序作为插入排序的拓展，对较大规模的 数据都可以达到很高的效率，但目前未得出其精确的渐近时间。堆排序利用了一种称为堆的数据 结构，可以在线性时间内完成建堆，且在O(nlog2n)内完成排序过程。快速排序基于分治的思想， 虽然最坏情况下的时间复杂度会达到O(n2),但快速排序的平均性能可以达到O(nlogn),在实际 应用中常常优于其他排序算法。归并排序同样基于分治的思想，但由于其分割子序列与初始序列 的排列无关，因此它的最好、最坏和平均时间复杂度均为O(nlog2n)。
- 从空间复杂度看：简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需借助常数 个辅助空间。快速排序需要借助一个递归工作栈，平均大小为
O(log2n),当然在最坏情况下可能会增长到O(n)。二路归并排序在合并操作中需要借助较多的辅助空间用于元素复制，大小为0(n),
虽然有方法能克服这个缺点，但其代价是算法会很复杂而且时间复杂度会增加。- 从稳定性看：插入排序、冒泡排序、归并排序和基数排序是稳定的排序算法，而简单选择排 序、快速排序、希尔排序和堆排序都是不稳定的排序算法。平均时间复杂度为O(nlogn)的稳定排
序算法只有归并排序，对于不稳定的排序算法，只需举出一个不稳定的实例即可。- 从适用性看：折半插入排序、希尔排序、快速排序和堆排序适用于顺序存储。直接插入排序、冒泡排序、简单选择排序、归并排序和基数排序既适用于顺序存储，又适用于链式存储。
7. 外部排序
① 外部排序指的是大文件的排序，即待排序的记录存储在外存中，待排序的文件无法一次性装入内存，需要在内存和外存之间进行多次数据交换，以达到排序整个文件的目的。
② 为减少平衡归并中外存读/写次数所采取的方法：增大归并路数和减少归并段个数。
③ 利用败者树增大归并路数。
④ 利用置换-选择排序增大归并段长度来减少归并段个数。 ⑤ 由长度不等的归并段进行多路平衡归并，需要构造最佳归并树。
许多应用中，经常需要对大文件进行排序，因为文件中的记录很多，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过 程中需要多次进行内存和外存之间的交换。这种排序算法就称为外部排序。
8. 一些常见结论
- 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法。【选快希堆】
- 冒泡排序、插入排序、归并排序、基数排序是稳定的排序算法。【直冒归基】
- 简单选择排序则与序列的初始状态无关