数据结构和算法基础之排序算法

排序算法作为算法的基础是学习算法很好的案例。众多的排序算法不仅体现了诸如递归、分治等算法的设计技巧,还包含了优先队列(二叉堆)等数据结构,是算法和数据结构很好的结合。

一、少量数据的排序算法

1.冒泡排序

冒泡排序应该是算法初学者最先接触的排序算法,它很好理解,就是将数从头开始和后面所有的数比较,如果后面的数比本身大或小就交换位置,这样每次就能找出最大或最小的元素,而这些元素也就像冒泡一样的被移动到数组的末尾。经过两个for循环后元素就有序了。核心代码如下:

1
2
3
4
5
6
7
for(int i=0;i<a.length;i++){
for(int j=i+1;j<a.length;j++){
if(a[i]<a[j]){
swap(a,i,j);
}
}
}

很显然,冒泡排序的时间复杂度是O(N²),如果问题规模很大的话,显然是不适合的。

2.插入排序

插入排序的思想也很简单,就是保证前n个数有序,随着n的增大最后整个数组就有序了。那如何保证前n个数有序呢?一次循环就可以搞定了,因为前(n-1)个数是有序的,那么把第n个数插入到合适的位置就可以了,这个插入操作可以通过比较操作完成,如果遇到比第n个数大的就交换,最后就可以将n插入到合适的位置了。核心代码如下:

1
2
3
4
5
6
for(int i=1;i<a.length;i++){
for(int j=0;j<i;j++){
if(a[i]<a[j])
swap(a,i,j);
}
}

插入排序和冒泡排序的时间复杂度一样,对于大规模的排序问题不推荐。

二、效率比较高的排序算法

1.快速排序

快速排序的思想是找到一个元素,把比这个元素大的元素移动到右边,小的移动到左边,然后递归地重复此过程。核心代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int partition(int[] arr, int left, int right) {
int pivotKey = arr[left];
int pivotPointer = left;

while(left < right) {
while(left < right && arr[right] >= pivotKey)
right --;
while(left < right && arr[left] <= pivotKey)
left ++;
swap(arr, left, right); //把大的交换到右边,把小的交换到左边。
}
swap(arr, pivotPointer, left); //最后把pivot交换到中间
return left;
}

public static void quickSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int pivotPos = partition(arr, left, right);
//通过上面的partition方法,一次排序后就出现:中间右边的数都比中间的基准数要大、中间左边的数都比中间的基准数要小得规律。这样接下来分两次排序:将中间左边的数进行快速排序、将中间右边的数进行快速排序即可。
quickSort(arr, left, pivotPos-1);
quickSort(arr, pivotPos+1, right);
}

快速排序的实现稍微复杂,但是效率可以达到O(N㏒(N))

2.堆排序

堆排序利用了二叉堆的特性,即二叉堆的所有节点都比它的子节点小,那么根节点就是最小的。每次取根节点,然后对二叉堆进行删除根节点操作,并对删除后的堆重新调整,把最小的元素再次调整到根节点。这样就按可以顺序取出所有元素。

3.归并排序

归并排序使用分而治之的思想,将需要排序的元素分成两组,对两组元素进行排序,在这个排序过程中使用递归的思想继续分组和排序,归并排序的核心是合并排好序的两组数据,通过比较对应位置的元素并将这两个元素按顺序存入新数组即可将两组有序数组合并为一个新的有序数组。

4.希尔排序

希尔排序又叫缩减增量排序,它先对间隔n的元素进行排序,然后间隔n/2,最后间隔1,这个间隔的选择对排序效率有很大影响