概述
常用排序算法
- 冒泡排序
- 插入排序
- 选择排序
- 归并排序
- 快速排序
冒泡排序
步骤
- 比较相邻元素，如果前面元素比后面大，调换位置
- 对每一对相邻元素执行同样操作，从开始第一对到最后一对。这样最后的元素是最大值
- 针对所有元素重复上述步骤，除了最后一个元素
- 持续每次对越来越少的元素重复上述步骤，直到没有任何一对元素需要比较
public static void swap(int[] A,int l,int r){
int temp =A[l];
A[l]=A[r];
A[r]=temp;
}
/**
* 冒泡排序
* 最差时间复杂度 ---- O(n^2)
* 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
* 平均时间复杂度 ---- O(n^2)
* 所需辅助空间 ------ O(1)
* 稳定性 ------------ 稳定
*
* @param A
* @param n
*/
public static void bubbleSort(int[] A, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (A[j] > A[j + 1]) {
swap(A, j, j + 1);
}
}
}
}
插入排序
步骤
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后 - 重复步骤2~5
/**
* 插入排序
* 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
* 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
* 平均时间复杂度 ---- O(n^2)
* 所需辅助空间 ------ O(1)
* 稳定性 ------------ 稳定
* @param A
* @param n
*/
public static void insertSort(int[] A,int n){
for(int i=1;i<n;i++){
for(int j=i;j>0;j--){
if(A[j-1]>A[j]){
swap(A, j-1, j);
}
}
}
}
选择排序
步骤
- 从第一个元素开始，选择最小的元素
- 把最小的元素与第一个元素交换，这样第一个元素就是最小
- 下一次从第二个元素开始找最小的元素，重复此步骤直到没有元素需要选择
/**
* 选择排序 最差时间复杂度 ---- O(n^2)
* 最优时间复杂度 ---- O(n^2)
* 平均时间复杂度 ---- O(n^2)
* 所需辅助空间 ------ O(1)
* 稳定性 ------------ 不稳定
*
* @param A
* @param n
*/
public static void selectSort(int[] A, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (A[min] > A[j]) {
min = j;
}
}
if (min != i) {
swap(A, min, i);
}
}
}
归并排序
步骤
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
/**
* 归并排序
* 最差时间复杂度 ---- O(nlogn)
* 最优时间复杂度 ---- O(nlogn)
* 平均时间复杂度 ---- O(nlogn)
* 所需辅助空间 ------ O(n)
* 稳定性 ------------ 稳定
*
* @param A
* @param left
* @param right
*/
public static void mergeSort(int A[], int left, int right) // 递归实现的归并排序(自顶向下)
{
if (left == right) // 当待排序的序列长度为1时，递归开始回溯，进行merge操作
return;
int mid = (left + right) / 2;
mergeSort(A, left, mid);
mergeSort(A, mid + 1, right);
merge(A, left, mid, right);
}
public static void merge(int[] A, int left, int mid, int right) {
int len = right - left + 1;
int[] temp = new int[len]; // 辅助空间O(n)
int index = 0;
int i = left; // 前一数组的起始元素
int j = mid + 1; // 后一数组的起始元素
while (i <= mid && j <= right) {
temp[index++] = A[i] <= A[j] ? A[i++] : A[j++]; // 带等号保证归并排序的稳定性
}
while (i <= mid) {
temp[index++] = A[i++];
}
while (j <= right) {
temp[index++] = A[j++];
}
for (int k = 0; k < len; k++) {
A[left++] = temp[k];
}
}
快速排序
步骤
- 从序列中挑出一个元素，作为"基准"(pivot).
- 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
- 对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
public static int Partition(int A[], int left, int right) // 划分函数
{
int pivot = A[right]; // 这里每次都选择最后一个元素作为基准
int tail = left - 1; // tail为小于基准的子数组最后一个元素的索引
for (int i = left; i < right; i++) // 遍历基准以外的其他元素
{
if (A[i] <= pivot) // 把小于等于基准的元素放到前一个子数组末尾
{
swap(A, ++tail, i);
}
}
swap(A, tail + 1, right); // 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组
// 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法
return tail + 1; // 返回基准的索引
}
/**
* 快速排序
* 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
* 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
* 平均时间复杂度 ---- O(nlogn)
* 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)
* 稳定性 ---------- 不稳定
*
* @param A
* @param left
* @param right
*/
public static void quickSort(int A[], int left, int right) {
if (left >= right)
return;
int pivot_index = Partition(A, left, right); // 基准的索引
quickSort(A, left, pivot_index - 1);
quickSort(A, pivot_index + 1, right);
}
总结
排序.png
