排序算法(一)

概述

总结一下常用的八大排序算法,大致的描述算法的原理和代码.以下皆假设N为待排序数组元素的个数.

插入排序(Insertion Sort)

基本思想

插入排序是最简单排序,由N-1次排序组成,从i=1至N-1次排序之后,保证序列a[0]至a[i]为已排序的状态.

即开始排序之前从a[0]至a[i-1]始终是已排序状态,每次把a[i]处的元素依次向前交换,直到a[0]至a[i]保证顺序.

代码实现

1
2
3
4
5
6
7
8
9
public void insertionSort(int[] a) {
int j;//保存待插入的角标
for (int i = 1; i < a.length; i++) {
int tmp = a[i];//tmp元素保存待插入的元素
for ( j = i; j > 0 && a[j - 1] < tmp; j--)
a[j] = a[j - 1];//依次将大于待排序值的元素向后移动
a[j] = tmp;//把待排序元素插入对应的位置
}
}

效率

如果序列是有序的,那么内层循环可以很快结束,效率很高.

  • 最好情况下时间复杂度 : O(N)

  • 平均情况下时间复杂度 : O(N^2).

希尔排序(Shell Sort)

基本思想

希尔排序通过比较相距一定间隔h的元素进行排序,对于每次排序后的序列来说都有a[i]<a[i+h].每一次排序的间隔h逐渐减小,直到h=1为止(即基本有序之后再对整个序列进行插入排序).

希尔排序的好处是,对于单纯的插入排序而言,在元素基本有序的情况下,会减少元素交换位置的次数,效率是很高的.

代码实现

1
2
3
4
5
6
7
8
9
10
11
public void shellSort(int[] a) {
int j;
for (int gap = a.length / 2; gap > 0; gap /= 2) {//元素间隔从序列的长度的一半每次减半,直到间隔为1
for (int i = gap; i < a.length; i++) {//对每个相隔gap距离的元素进行插入排序
int tmp = a[i];
for (j = i; j >= gap && tmp < a[j - gap]; j -= gap)
a[j] = a[j - gap];
a[j] = tmp;
}
}
}

效率

希尔排序编程很简单,但是分析起来却很复杂,不同的增量因子的选择会影响算法的效率.实践中证明希尔排序的性能是完全可以接受,即使是数以万计的N仍成立.

  • 最坏情况下时间复杂度 : O(N^2).

归并排序

基本概念

归并算法的基本排序方法是依次比较两个已排序的子序列的头指针的元素,将更小的元素放入结果序列的头指针指向的位置,并后移结果序列的头指针.

归并排序是递归算法一个好的示例,很好的体现了”分而治之”的思想:对待排序序列分成左右两个子序列,依次分下去,直到不能再分;再对最小子序列进行前述排序,依次将排序好的子序列合并,直到待排序列的左右子序列合并完成.

代码实现

1
2
坚持原创技术分享,您的支持将鼓励我继续创作!