衡量算法的指标
时间复杂度十大排序算法比较
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
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
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
)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
highint
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小的值, 然后交换;
快速排序的优化:
对于小数组来说, 快速排序不如插入排序, 所以当数组比较少时, 可以切换到插入排序迪杰斯特拉的"三向切分的快速排序"(<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
(j1
)) { 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
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
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
10
, k -1
) %10
; }private
static
void
int
[] a) { System.out
.println(Arrays.toString(a)); } }/<code>