稳定的排序
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 冒泡排序 | 最差、平均都是O(n^2)，最好是O(n) | 1 |
| 插入排序 | 最差、平均都是O(n^2)，最好是O(n) | 1 |
| 归并排序 | 最差、平均和最好都是O(nlog n) | O(n) |
不稳定的排序
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 选择排序 | 最差、平均都是O(n^2) | 1 |
| 希尔排序 | O(nlog n) | 1 |
| 快速排序 | 平均是O(nlog n)，最坏情况下是O(n^2) | O(log n) |
冒泡排序
/**
* 冒泡排序原理：从头部开始，两两对比，并交换调整更大（小）值在数组中的位置，
* 把未有序部分中最大（小）值移动到有序部分的头部。 * 就像“冒泡”一样，把无序部
分中的最大（小）值，移动到有序部分。
*
* @author Affy
* @date 2018-09-20
*/
public class BubbleSort {
public static void bubbleSort(int[] source) {
int unSortIndex = 0;
int sortHeadIndex = source.length - 1;
System.out.print("before sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
boolean exchange = false;
int times = 0;
for (int high = sortHeadIndex; high > unSortIndex; high--) {
exchange = false;
times++;
//两两，把更大的值往后“冒”，直到有序序列的头部位置
for (int low = 0; low < sortHeadIndex; low++) {
if (source[low] > source[low + 1]) {
int temp = source[low];
source[low] = source[low + 1];
source[low + 1] = temp;
exchange = true;
}
}
//如果存在某一次排序没有发生交换，证明无序区中所有元素都有序，可以提前终止算法了
if (!exchange) {
break;
}
}
System.out.print("\n第" + times + "趟完成排序" + "\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
bubbleSort(source);
}
}
- 算法的最好时间复杂度
若文件的初始状态是有序的，则一次扫描就可完成排序，则比较次数C=n-1，移动次数M=0；也就是时间复杂度为O(n)。 - 算法的最坏时间复杂度
若文件的初始状态是逆序，则需要进行n-1次排序。每次排序要进行n-i次关键字的比较（1<= i <= n-1）,每次比较都必须移动记录三次来达到交换记录位置。此时比较次数C=n(n-1)/2 = O(n^2 )，交换次数M=3n(n-1)/2 = O( n^2 )。也就是时间复杂度为O(n^2)。
选择排序
/**
* 每趟排序，从未排序序列中选择最小（大）值，放到有序序列的末尾
*
* @author Affy
* @date 2018-09-21
*/
public class SelectSort {
public static void selectSort(int[] source) {
System.out.print("before sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
for (int low = 0; low < source.length - 1; low++) {
//每次遍历，找到未排序队列中的最小值，并标记其下标
int minimumIndex = low;
for (int high = low + 1; high < source.length; high++) {
if (source[minimumIndex] > source[high]) {
minimumIndex = high;
}
}
if (minimumIndex != low) {
int temp = source[low];
source[low] = source[minimumIndex];
source[minimumIndex] = temp;
}
}
System.out.print("\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
selectSort(source);
}
}
选择排序的交换操作介于0和(n-1)次之间；比较操作为n(n-1)/2次之间；赋值操作介于0和3(n-1)次之间；平均复杂度为O(n^2)
插入排序
/**
* <li>从第一个元素开始，该元素可以认为已经被排序</li>
* <li>取出下一个元素，在有序序列中从后往前扫描</li>
* <li>如果取出的新元素比当前元素小，则将当前元素移动到下一位置</li>
* <li>重复上一步，直到新元素小于或等于前一个元素，记录该位置，并将新元素插入到该位置</li>
*
* @author Affy
* @date 2018-09-21
*/
public class InsertSort {
public static void insertSourt(int[] source) {
System.out.print("before sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
for (int low = 0; low < source.length - 1; low++) {
//取出有序队列末尾的后一个元素，从后往前遍历。如果比当前元素小，则将当前元素移动一个位置(其实就是交换两元素)
for (int high = low + 1; high > 0 && source[high] < source[high - 1]; high--) {
int temp = source[high];
source[high] = source[high-1];
source[high-1] = temp;
}
}
System.out.print("\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
insertSourt(source);
}
}
如果目标是升序排列，那么在最好和最坏的情况下：
- 最好：目标序列已经是升序。在这种情况下，只需要n-1次比较。因此复杂度是O(n)。
- 最坏：目标序列是降序。此时，共需要进行n(n-1)/2次比较，赋值操作时比较次数加上n-1次。因此复杂度是O(n ^ 2)
平均来说，插入排序算法复杂度为O(n^2)。因此不适合对于数据量比较大的排序应用。但是，如果量级小于千时，那么插入排序还是一个不错的选择。
希尔排序
shell排序分组
可参考：图解排序之希尔排序
package com.affy.testapp;
/**
* 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，
* 每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
*
* @author Affy
* @date 2018-09-25
*/
public class ShellSort {
public static void shellSort(int[] source, int gap) {
System.out.print("\nbefore sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
int high, low;
//从第一个间隔开始，依次对source[gap]...source[n]进行处理，每次比较都取source[high-gap],这样就能确保覆盖到每个元素
for (low = gap; low < source.length; low++) {
for (high = low; high - gap >= 0 && source[high - gap] > source[high]; high -= gap) {
int temp = source[high];
source[high] = source[high - gap];
source[high - gap] = temp;
}
}
System.out.print("\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
int increment = source.length;
do {
increment /= 2;
shellSort(source, increment);
} while (increment > 0);
}
}
快速排序
1
2
3
4
5
6
7
8
总时序.jpg
/**
* 快排采用了分治法的策略进行排序
* <p>分治法：将原问题分解为若干规模更小但结构与原问题相似的子问题，
递归地解这些子问题，然后将这些子问题的解组合为原问题的解</p>
* <p>
* 快排基本思想：
* <ol>
* <li>分解。选取基准，使得基准左边为小于或等于基准值，右边大于或等于基准值</li>
* <li>求解。递归调用快排对左右子区间R[low,pivotPos-1]和R[pivotPos+1,high]进行排序</li>
* <li>组合。上一步做完之后，其实左右子区间已经有序，故无需做什么</li>
* </ol>
* </p>
*
* @author Affy
* @date 2018-09-26
*/
public class QuickSort {
private static void quickSort(int[] source, int low, int high) {
int pivot;//基准位置的记录
if (low < high) {
int i = low;
int j = high;
pivot = source[i];
while (i < j) {
//从高处往左遍历，直到找到第一个关键字小于pivot的记录source[j]
while (j > i && source[j] >= pivot) {
j--;
}
//接着从i开始，从低处往右遍历，直到找到第一个关键字大于pivot的记录source[i]。
while (i < j && source[i] <= pivot) {
i++;
}
//此时可交换source[i]和source[j]
if (i < j) {
source[i] = source[i] ^ source[j];
source[j] = source[i] ^ source[j];
source[i] = source[i] ^ source[j];
}
}
//当i == j时，i就是需要的基准位置，它的左边小于它，右边大于它,交换source[low]和source[i]
source[low] = source[i];
source[i] = pivot;
quickSort(source, low, i - 1);
quickSort(source, i + 1, high);
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
System.out.print("before sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
quickSort(source, 0, source.length - 1);
System.out.print("\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
}
这里交换操作用了亦或操作的小技巧，可参考：https://blog.csdn.net/heathyhuhu/article/details/12744407
归并排序
分治
合并
图片出处
/**
* 归并排序。使用分割的方法将无序的序列分成一个一个已经排好序的子序列，
* 然后利用归并的方法将一个个子序列合并成排好序的序列。 每次分割的时候，
* 首先分成两份，然后再把2份分成4份，一次分割直到分割成一个一个数据。
*
* @author Affy
* @date 2018-09-26
*/
public class MergeSort {
static void mergeSort(int[] source, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
//分组，不断递归直到子序列只包含一个元素
mergeSort(source, start, mid);
mergeSort(source, mid + 1, end);
//合并
merge(source, start, mid, mid + 1, end);
}
}
static void merge(int[] source, int start1, int end1, int start2, int end2) {
//新建和两个需要合并的数组大小一样的临时数组存放合并结果
int[] temp = new int[end2 - start1 + 1];
int i = start1, j = start2, k = 0;
//合并两个数组，按照从小到大的顺序排列
while (i <= end1 && j <= end2) {
if (source[i] < source[j]) {
temp[k++] = source[i++];
} else {
temp[k++] = source[j++];
}
}
//剩余元素存放
while (i <= end1) {
temp[k++] = source[i++];
}
while (j <= end2) {
temp[k++] = source[j++];
}
//将临时数组替换到原数组
k = 0;
for (i = start1; i <= end2; i++) {
source[i] = temp[k++];
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
System.out.print("before sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
mergeSort(source, 0, source.length - 1);
System.out.print("\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
}
网友评论