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