排序算法
基本的排序算法
插入类排序
插入类排序基本思想在于, 每次将一个元素插入到前面已经排好序的子序列中, 包括直接插入排序、折半插入排序、希尔排序
直接插入排序
- 基本思想: 一个数组, 左边有序(起始只有一个元素), 把右边元素依次插入到左边的有序表
- 算法步骤:
- 找到元素
L[i]在左边有序表L[1 ~ i-1]的插入位置k - 将
L[k ~ i-1]所有元素全部后移一个位置(必须临时存放原来的L[i]) - 把元素
L(i)复制到L[k]
- 找到元素
- 算法描述:
// 直接插入排序
public void insertSort(int A[], int n) {
int i, j;
for (i = 1; i <= n - 1; i++) { // 依次将A[1]~A[n-1]插入到前面已排序序列(初始的有序表只有A[0])
if (A[i] < A[i - 1]) { // 若A[i]小于前驱, 需将A[i]插入有序表
int temp = A[i]; // 临时存放待插入元素
for (j = i - 1; j >= 0 && temp < A[j]; --j) { // 向前查找待插入位置
A[j + 1] = A[j]; // 向后挪位
}
A[j + 1] = temp; // 复制到插入位置
}
}
}
- 空间复杂度:
O(1), 借助于了一个临时存放单元 - 时间复杂度:
O(n^2), 最好情况下, 元素已经有序, 时间复杂度为O(n) - 稳定性: 稳定
- 适用场景: 基本有序
折半插入排序
- 基本思想: 也是左边有序, 右边依次插入有序表, 不同的是找插入位置
k时, 使用折半查找法 - 算法描述:
// 折半插入排序(递增排序)
public void binaryInsertSort(int A[], int n) {
for (int i = 1; i <= n - 1; i++) { // 依次将A[1]~A[n-1]插入到前面已排序序列
int tmp = A[i]; // 临时存放待插入元素
int low = 0; // 折半查找的范围
int high = i - 1;
while (low <= high) { // 折半查找(low == high 总会发生)
int mid = (low + high) / 2; // 取中间点
if (A[mid] > tmp) { // 查找左半子表
high = mid - 1;
} else { // 查找右半子表
low = mid + 1;
}
}
// 程序到这里会出现 high + 1 == low
for (int j = i - 1; j >= high + 1; --j) { // 统一移动元素, 空出插入位置
A[j + 1] = A[j]; // 向后挪位
}
A[high + 1] = tmp;
}
}
- 空间复杂度:
O(1) - 时间复杂度:
O(n^2), 仅减少了比较次数, 大约为O(nlogn)(log表示以2为底的对数), 且比较次数与初始顺序无关 - 稳定性: 稳定
- 适用场景: 数据量不大
交换类排序
交换类排序的基本思想在于, 根据两个元素的比较结果来交换两个元素在序列中的位置, 包括冒泡排序和快速排序
冒泡排序
- 基本思想: 从后向前(也可从前向后)依次比较相邻两元素, 若为逆序则交换, 这样一趟冒泡会把最小的元素交换到第一个位置; 下一趟冒泡时, 第一个元素就不再参与了, 这样每次都把最小元素交换到前面, 总共进行
n-1趟冒泡就可以了. - 算法描述:
// 冒泡排序(递增排序)
public void bubbleSort(int A[], int n) {
for (int i = 0; i < n - 1; i++) { // 总共需要n-1趟冒泡
boolean flag = false; // 用于记录本趟是否发生了交换, 只要有一趟没发生交换, 就说明已经有序了
for (int j = n - 1; j > i; j--) { // 一趟冒泡
if (A[j - 1] > A[j]) { // 相邻元素比较
swap(A, j - 1, j); // 交换
flag = true;
}
}
if (!flag) { // 如果这趟没发生交换, 说明已经有序了
return;
}
}
}
- 空间复杂度:
O(1) - 时间复杂度:
O(n^2), 最好情况下, 元素已经有序, 时间复杂度为O(n) - 稳定性: 稳定
- 适用场景: 基本有序
- 另附关于交换两个单元的方法:
// 借助临时单元
int tmp = a;
a = b;
b = tmp;
// 直接交换
a = a + b; // 注意有可能溢出
b = a - b;
a = a - b;
// 位操作交换
a = a ^ b;
b = a ^ b;
a = a ^ b;
快速排序
- 基本思想: 基于分治法, 在n个元素中任取一个元素
pivot(一般为第一个元素)作为基准, 一趟排序后把数据分成两部分, 左边L[0 ~ k-1]和 右边L[k+1 ~ n-1], 使得左边元素都小于pivot, 右边都大于pivot, 而pivot直接复制到L[k]上, 这个过程成为一趟快排; 然后对左子表和右子表分别进行上述过程, 直到每部分只有一个元素或为空为止, 即所有元素都放在了最终位置上. - 算法描述:
// 快速排序
public static void quickSort(int A[], int left, int right) {
if (left < right) { // 跳出递归的条件
int pivotPos = partition(A, left, right); // 划分函数, 找到pivot的位置
quickSort(A, left, pivotPos - 1); // 排序左子表
quickSort(A, pivotPos + 1, right); // 排序右子表
}
}
// 划分函数, 一趟排序的过程
private static int partition(int A[], int left, int right) {
int pivot = A[left]; // 任取一个元素作为基准, 这里用第一个元素作为基准
while (left < right) { // 循环跳出的条件
while (left < right && A[right] >= pivot) --right; // 从后向前找到第一个小于pivot的元素
A[left] = A[right]; // 把小于pivot的元素换到左边
while (left < right && A[left] <= pivot) ++left; // 从前向后找到第一个大于pivot的元素
A[right] = A[left]; // 把大于pivot的元素换到右边
}
// 跳出循环总会有 left == right
A[left] = pivot;
return left;
}
- 空间复杂度:
O(n), 栈深度最好为log(n+1), 最坏为n-1, 平均栈深度O(logn) - 时间复杂度: 最好
O(nlogn), 最坏(有序时最坏)O(n^2), 平均接近最好情况;快排是是所有排序算法中平均性能最优的 - 稳定性: 不稳定
选择类排序
选择类排序的基本思想在于, 每趟都从待排序列中选取一个最小值作为序列的第i个元素,直到第n-1趟, 待排序列只剩下一个元素. 包括简单选择排序和堆排序
简单选择排序
- 基本思想: 第
i趟从L[i ~ n]中选择关键字最小的元素与L[i]交换, 这样每趟都可确定一个元素的最终位置, 经过n-1趟就可以使整个序列有序. - 算法描述:
// 简单选择排序
public void selectSort(int A[], int n) {
for (int i = 0; i < n - 1; i++) { // 一共进行 n-1 趟
int min = i; // 记录最小元素位置
for (int j = i + 1; j < n; j++) { // 从 A[i+1 ~ n-1]中选择最小元素
if (A[j] < A[min]) { // 更新最小元素位置
min = j;
}
}
if (min != i) { // 最小的与第i个位置交换
swap(A, i, min);
}
}
}
- 空间复杂度:
O(1) - 时间复杂度:
O(n^2) - 稳定性: 不稳定
堆排序
- 特点: 在排序过程中, 把
L[1 ~ n]看成是一颗完全二叉树的顺序存储结构, 利用完全二叉树中父节点和子节点的内在关系, 在当前无需区中选择关键字最大(或最小)的元素 - 完全二叉树: 若二叉树除最后一层外, 其它各层的结点数都达到最大个数, 最后一层所有的结点都连续集中在最左边, 这就是完全二叉树
- 小根堆:
L[1~n]满足L[i]<=L[2i]且L[i]<=L[2i+1] - 大根堆:
L[1~n]满足L[i]>=L[2i]且L[i]>=L[2i+1] - 大根堆示例:(左右兄弟结点没有大小关系)
- 算法思想: 堆排序主要包括两个步骤
- 创建初始堆: 堆排序的关键就是构造初始堆.
n个结点的完全二叉树, 最后一个结点一定是n/2个结点的子结点, 所以我们从n/2结点开始保证它是一个堆, 然后不断向前调整, 保证每个结点都大于左右子结点(不大于则交换). 当然在过程中可能因为交换破坏了下一级的堆, 这时要继续调整下一级堆, 保证子树构造成堆为止. 反复调整直到根结点. - 排序输出: 大根堆里堆顶元素一定是最大的, 因此每次输出堆顶元素, 然后把堆顶元素与堆底元素交换, 在把剩余的元素(刚才的堆顶元素已经在堆底, 可调整的元素个数-1)调整成堆, 再次输出堆顶元素, 依次类推, 就是按由大到小的顺序把元素全部输出了.
- 创建初始堆: 堆排序的关键就是构造初始堆.
- 算法描述:
// 创建大根堆
public void buildMaxHeap(int A[], int n) { // n为参与建堆的元素个数
for (int i = n / 2; i >= 0; i--) { // 从n/2到0, 依次调整
adjustDown(A, i, n);
}
}
// 向下调整(可用于删除元素)
public void adjustDown(int A[], int k, int n) { // k为要调整结点下标, n为要调整的元素个数
int temp = A[k];
for (int i = k * 2; i < n; i = i * 2) { // 调整k为根的子树
if (k == 0) { // 如果下标是从0开始的, 则0的左子结点下标为1
i = 1;
}
if (i < n - 1 && A[i] < A[i + 1]) { // 左右子结点中, 取较大的那个结点跟temp比
i++;
}
// i是左右子结点中较大的那个
if (temp >= A[i]) { // temp >= A[i]时, 此时的k是temp应该调整到的位置
break; // 找到temp该在的位置时, 筛选结束
} else { // 没找到temp该在的位置时, 还要继续调整
A[k] = A[i]; // 先把A[i]调整到父结点上
k = i; // 修改k值, 以便继续向下筛选
}
} // 出了循环, k这颗子树就调整完毕了
A[k] = temp;
}
// 堆排序
public void heapSort(int A[], int n) { // 对前n个元素建堆
buildMaxHeap(A, n); // 创建初始堆
for (int i = n - 1; i > 0; i--) { // n-1趟交换建堆过程
System.out.println(A[0]); // 输出
swap(A, 0, i); // 交换堆顶和堆底元素, 为的是把堆底元素撇出去
adjustDown(A, 0, i - 1); // 把剩余的 i-1 个元素调整成堆
}
System.out.println(A[0]); // 把最后一个元素输出
}
- 堆的删除和插入
- 堆顶删除, 把堆顶和堆底交换, 对根结点进行向下调整(剩余元素)
- 堆底插入, 再对这个结点进行向上调整. 向上调整的算法如下:
// 向上调整(可用于添加元素)
public void adjustUp(int A[], int n) { // 添加元素只能从堆底添加, n为要调整的元素个数, 所以添加的元素下标k=n-1
int k = n - 1; // 新添加元素的下标
int temp = A[k];
int p = n / 2; // p为双亲结点
while (p >= 0 && A[p] < temp) { // 若结点大于双亲结点, 则将双亲结点向下调, 并继续向上比较
A[k] = A[p]; // 双亲结点下调
k = p; // 记录调整到的节点位置
p = k / 2; // 继续向上比较
if (k == 0) { // 下标从0开始的话, 必须有这一步, 不然会出现死循环
break;
}
} // 出循环时的n即为最终应该在的位置
A[k] = temp;
}
- 添加元素的一个例子:
@Test
public void mainTest() {
int A[] = {1, 2, 3, 4, 5, 5, 6, 7, 8, 9}; // 一共10个元素
buildMaxHeap(A, A.length - 1); // 前9个元素建堆
adjustUp(A, A.length); // 添加第10个元素(下标为9)进去
// 排序输出
for (int i = A.length - 1; i > 0; i--) { // n-1趟交换建堆过程
System.out.println(A[0]); // 输出
swap(A, 0, i); // 交换堆顶和堆底元素, 为的是把堆底元素撇出去
adjustDown(A, 0, i - 1); // 把剩余的 i-1 个元素调整成堆
}
System.out.println(A[0]); // 把最后一个元素输出
}
- 空间复杂度:
O(1) - 时间复杂度: 建堆
O(n), 调整O(h), 平均O(nlogn) - 稳定性: 不稳定
归并排序
- 算法思想: 把两个有序表合并成一个有序表
- 算法描述:
// 归并排序 A[left, right]
public void mergeSort(int A[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2; // 从中间划分两个序列
mergeSort(A, left, mid); // 左边递归排序
mergeSort(A, mid + 1, right); // 右边递归排序
merge(A, left, mid, right); // 归并
}
}
// A[left, mid] 和 A[mid+1, right] 各自有序, 把他们合并成一个有序表
public void merge(int A[], int left, int mid, int right) {
int i, j, k;
int B[] = new int[A.length]; // 这是个辅助单元
// 把A[left, right]复制到B中
for (i = left; i <= right; i++) {
B[i] = A[i];
}
// i表示左边, j表示右边, k表示合并后的下标
for (i = left, j = mid + 1, k = i; i <= mid && j <= right; k++) {
if (B[i] < B[j]) { // 比较B左右两端中的元素大小, 小的复制到A中
A[k] = B[i++];
} else {
A[k] = B[j++];
}
}
// 若左边未复制完, 复制
while (i <= mid) {
A[k++] = B[i++];
}
// 若右边未复制完, 复制
while (j <= right) {
A[k++] = B[j++];
}
}
- 空间复杂度:
O(n) - 时间复杂度:
O(nlogn),2路归并底数为2,K路归并底数为k - 稳定性: 稳定