衡量算法的指标
- 时间复杂度 : 执行这个算法需要消耗的时间
- 空间复杂度 : 这个算法需要占用多少内存空间
- 稳定性 : 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的.
- In-place 是指不占用额外内存, Out-place 需要占用额外内存.
十大排序算法比较
- 冒泡排序, 选择排序 , 插入排序, 希尔排序, 归并排序, 快速排序 , 堆排序都属于 比较排序 比较排序的优势是, 适用于各种规模的数据, 也不在乎数据的分布, 都能进行排序
- 计数排序, 桶排序, 基数排序 属于 非比较排序 非比较排序只要确定每个元素之前的已有的元素个数即可, 所有一次遍历即可解决。算法时间复杂度O(n), 但需要占用空间来确定唯一位置. 所以对数据规模和数据分布有一定的要求.
Bubble sort(冒泡排序)
public class BubbleSort {
public static void main(String[] args) {
Integer [] arr = {18, 23, 11, 1, 9, 25, 33, 46};
sort(arr);
print(arr);
}
/**
* sort a comparable array
* @param a the comparable array
*/ private static void sort(Comparable[] a) {
int length = a.length;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if (a[i].compareTo(a[j]) > 0) {
exch(a, i, j);
}
}
}
}
private static void exch(Comparable[] a, int i, int min) {
Comparable temp = a[i];
a[i] = a[min];
a[min] = temp;
}
private static void print(Comparable[] a) {
System.out.println(Arrays.toString(a));
}
}
Selection sort(选择排序)
选择排序, 对于长度为N的数组, 需要1 + 2 + … + (N-1) = N(N-1)/2 约等于N2/2次比较, 需要N次交换.
选择排序的步骤:
- 从第一个元素开始逐个和后面的元素比较, 然后找到最小元素的下标.
- 交换当前元素和最小元素.
public class SelectionSort {
// 注:之后所有的排序都使用该方法
public static void main(String[] args) {
Integer [] arr = {18, 23, 11, 1, 9, 25, 33, 46};
sort(arr);
print(arr);
}
/**
* sort a comparable array
* @param a the comparable array
*/ private static void sort(Comparable[] a) {
int length = a.length;
for (int i = 0; i < length; i++) {
int min = i;
for (int j = i + 1; j < length; j++) {
if (a[j].compareTo(a[min]) < 0) {
min = j;
}
}
exch(a, i, min);
}
}
// 注:之后所有的排序都使用该方法
private static void exch(Comparable[] a, int i, int min) {
Comparable temp = a[i];
a[i] = a[min];
a[min] = temp;
}
// 注:之后所有的排序都使用该方法
private static void print(Comparable[] a) {
System.out.println(Arrays.toString(a));
}
} Inserting sort(插入排序)
插入排序最坏需要进行N2/2次比较和N2/2次交换. 最好情况是只需要进行N – 1次比较和0次交换.
注: 适合接近有序的数组进行排序, 类似于打扑克抓牌的过程
public class InsertionSort {
/**
* sort a comparable array
* @param a the comparable array
*/ private static void sort(Comparable[] a) {
int length = a.length;
for (int i = 1; i < length; i++) {
for (int j = i; j > 0; j--) {
if (a[j].compareTo(a[j-1]) < 0) {
exch(a, j, j - 1);
}
}
}
}
} Shell sort(希尔排序)
希尔排序是对插入排序的一种改进 (减少了元素的移动). 希尔排序的思想是使数组中任意间隔为h的元素都是有序的.它权衡了数组的规模和有序性.
该算法主要是, h的选择.
public class ShellSort {
/**
* sort a comparable array
* @param a the comparable array
*/ private static void sort(Comparable[] a) {
int length = a.length;
int h = 1;
while(h < length/3) {
h = 3*h + 1;
}
while (h >= 1) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h; j-=h) {
if (a[j].compareTo(a[j-h]) < 0) {
exch(a, j, j - h);
}
}
}
h = h/3;
}
}
} Merge sort(归并排序)
归并排序将数组分成两个子数组分别排序, 并将有序的子数组归并以将整个数组排序;
public class MergeSort {
private static Comparable[] aux;
public static void main(String[] args) {
Integer [] arr = {18, 23, 11, 1, 9, 25, 33, 46};
sort(arr);
print(arr);
}
private static void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
/**
* sort a comparable array
* @param a the comparable array
*/ private static void sort(Comparable[] a, int low, int high) {
if (high <= low) {
return;
}
int mid = low + (high - low)/2;
sort(a, low, mid);
sort(a, mid + 1, high);
merge(a, low, mid, high);
}
private static void merge(Comparable[] a, int low, int mid, int high) {
int i = low, j = mid + 1;
for (int k = low; k <= high; k++) {
aux[k] = a[k];
}
for (int k = low; k <= high; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > high) {
a[k] = aux[i++];
} else if (aux[j].compareTo(aux[i]) < 0) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
private static void exch(Comparable[] a, int i, int min) {
Comparable temp = a[i];
a[i] = a[min];
a[min] = temp;
}
private static void print(Comparable[] a) {
System.out.println(Arrays.toString(a));
}
} Quick sort(快速排序)
快速排序和归并排序是互补的, 快速排序是一种分治的排序算法, 它将一个数组分成两个子数组, 将两部分独立地排序; 当两个子数组都有序时整个数组也就自然有序了.
注: 此排序的关键是 partition 方法, 找到partition值. partition必须满足
- 左边的元素都小于等于partition值 ;
- 右边的元素都大于等于partition值 ;
查找的方法是从左边扫描比partition大的值,从数组尾部扫描比partition小的值, 然后交换;
快速排序的优化:
- 对于小数组来说, 快速排序不如插入排序, 所以当数组比较少时, 可以切换到插入排序
- 迪杰斯特拉的”三向切分的快速排序” ( TODO )
public class QuickSort {
private static void sort(Comparable[] a) {
sort(a, 0, a.length - 1);
}
/**
* sort a comparable array
* @param a the comparable array
*/ private static void sort(Comparable[] a, int low, int high) {
if (high <= low) {
return;
}
int j = partition(a, low, high);
sort(a, low, j);
sort(a, j+1, high);
}
private static int partition(Comparable[] a, int low, int high) {
int i = low, j = high + 1;
Comparable v = a[low];
while (true) {
// 扫描左右, 检查扫描是否结束并交换元素
while (a[++i].compareTo(v) < 0) {
if (i == high) {
break;
}
}
while (a[--j].compareTo(v) > 0) {
if (j == low) {
break;
}
}
if (i >= j) {
break;
}
exch(a, i, j);
}
exch(a, low, j);
return j;
}
} Heap sort(堆排序)
堆排序分为两个阶段:
- 堆的构造阶段, 将原始数组安排进一个堆中
- 下沉阶段, 递减取出所有元素并得出排序结果
public class HeapSort {
public static void main(String[] args) {
Integer [] arr = {18, 23, 11, 1, 9, 25, 33, 46};
sort(arr);
print(arr);
}
/**
* sort a comparable array
* @param a the comparable array
*/ private static void sort(Comparable[] a) {
int length = a.length;
// 堆的构造
for (int k = length/2; k >= 1; k--) {
sink(a, k, length);
}
// 堆的排序
while (length > 1) {
exch(a, 1, length--);
// 取出最大元素
sink(a, 1, length);
}
}
/**
* 堆的下沉操作, 就是将堆构造成任意一个结点都比他的子节点要大
* @param a the comparable array
* @param k the number to sink
*/ private static void sink(Comparable[] a, int k, int length) {
while (2 * k <= length) {
// j为左子节点
int j = 2 * k;
// 如果左子节点没有越界, 并且左子节点比右子节点小
// 就选择左右节点中较大的子节点
if (j < length && less(a, j, j+1)) {
j++;
}
// 如果需要sink的节点比最大的节点还要大, 就退出
if (!less(a, k, j)) {
break;
}
// 否则就交换两个节点
exch(a, k, j);
// 重新获取k的位置进行比较
k = j;
}
}
private static boolean less(Comparable[] a, int i, int j) {
return a[i - 1].compareTo(a[j - 1]) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i - 1];
a[i - 1] = a[j - 1];
a[j - 1] = temp;
}
private static void print(Comparable[] a) {
System.out.println(Arrays.toString(a));
}
} Counting sort(计数排序)
计数排序分为4步骤:
- 得到数列的最大值与最小值，并算出差值d
- 创建统计数组并计算统计对应元素个数
- 统计数组变形，后面的元素等于前面的元素之和
- 倒序遍历原始数组，从统计数组找到正确位置，输出到结果数组
public class CountingSort {
public static void main(String[] args) {
int [] arr = {18, 23, 11, 1, 9, 25, 33, 46};
print(sort(arr));
}
/**
* sort a comparable array
* @param array the comparable array
*/ private static int[] sort(int[] array) {
//1.得到数列的最大值与最小值，并算出差值d
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
if(array[i] < min) {
min = array[i];
}
}
int d = max - min;
//2.创建统计数组并计算统计对应元素个数
int[] countArray = new int[d + 1];
for (int i = 0; i < array.length; i++) {
countArray[array[i] - min]++;
}
//3.统计数组变形，后面的元素等于前面的元素之和
int sum = 0;
for (int i = 0; i < countArray.length; i++) {
sum += countArray[i];
countArray[i] = sum;
}
//4.倒序遍历原始数组，从统计数组找到正确位置，输出到结果数组
int[] sortedArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
sortedArray[countArray[array[i] - min] - 1] = array[i];
countArray[array[i] - min]--;
}
return sortedArray;
}
private static void print(int[] a) {
System.out.println(Arrays.toString(a));
}
} Bucket sort(桶排序)
桶排序步骤:
- 找出数组最大值, 得到桶的数量
- 把数字出现的次数放入对应数组中
- 打印次数大于0的数组元素
public class BucketSort {
public static void main(String[] args) {
int [] arr = {18, 23, 11, 1, 9, 25, 33, 46};
sort(arr);
print(arr);
}
/**
* sort a comparable array
* @param arr the comparable array
*/ private static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 获取数组的最大值, 来定义bucket的个数
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
// 统计每个元素出现的次数
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
// 遍历桶中大于0的元素
int i = 0;
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[i++] = j;
}
}
}
private static void print(int[] a) {
System.out.println(Arrays.toString(a));
}
} Radix sort(基数排序)
基数排序的步骤:
- 求出数组中所有数据的最大位数
- 循环按照每位上的数据进行排序
public class RadixSort {
public static void main(String[] args) {
int [] arr = {18, 23, 11, 1, 9, 25, 33, 46, 189, 389};
sort(arr);
print(arr);
}
/**
* sort a int array
* @param arr the int array
*/ private static void sort(int[] arr) {
//count数组用来计数
int[] count = new int[arr.length];
// bucket用来当桶（在下面你就理解了什么是桶了），放数据，取数据
int[] bucket = new int[arr.length];
int digits = getMaxDigits(arr);
// k表示第几位，1代表个位，2代表十位，3代表百位
for(int k = 1; k <= digits; k++) {
// 把count置空，防止上次循环的数据影响
for(int i = 0; i < arr.length; i++) {
count[i] = 0;
}
// 分别统计第k位是0,1,2,3,4,5,6,7,8,9的数量
// 以下便称为桶
// 即此循环用来统计每个桶中的数据的数量
for (int value : arr) {
count[getFigure(value, k)]++;
}
// 利用count[i]来确定放置数据的位置
for(int i = 1; i < arr.length;i++) {
count[i] = count[i] + count[i-1];
}
// 执行完此循环之后的count[i]就是第i个桶右边界的位置
// 利用循环把数据装入各个桶中，注意是从后往前装
// 这里是重点，一定要仔细理解
for (int i = arr.length - 1; i >= 0; i--) {
int j = getFigure(arr[i], k);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
// 将桶中的数据取出来，赋值给arr
for(int i = 0, j = 0; i < arr.length; i++, j++) {
arr[i] = bucket[j];
}
}
}
// 获取数组中数字的最大位数
private static int getMaxDigits(int[] a) {
int maxDigits = 1;
for (int value : a) {
int digits = 1;
while (value / (int) (Math.pow(10, digits)) > 0) {
digits++;
}
maxDigits = Math.max(maxDigits, digits);
}
return maxDigits;
}
// 此函数返回整型数i的第k位是什么
private static int getFigure(int value, int k) {
return value / (int) Math.pow(10, k - 1) % 10;
}
private static void print(int[] a) {
System.out.println(Arrays.toString(a));
}
} 十大排序应用场景
- 若n较小(如n≤50)，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好, 因为当数组基本有序时, 直接插入移动次数较少; 否则应选择Selection sort为宜.
- 若文件初始状态`基本有序(指正序), 则应选用插入排序, 冒泡或随机的快速排序为宜
- 若n较大，则应采用时间复杂度为O(nlgn)的排序方法: 快速排序 , 堆排序 或 归并排序 快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时, 快速排序的平均时间最短.堆排序所需的辅助空间少于快速排序, 并且不会出现快速排序可能出现的最坏情况. 但这两种排序都是不稳定的.若要求排序稳定, 则可选用归并排序. 但从单个记录起进行两两归并的排序算法并不值得提倡, 通常可以将它和直接插入排序结合在一起使用. 先利用直接插入排序求得较长的有序子序列, 然后再两两归并之. 因为直接插入排序是稳定的, 所以改进后的归并排序仍是稳定的
