数据结构与算法:排序算法
一、冒泡排序
1.排序原理
1)冒泡排序只会操作相邻的两个数据。
2)对相邻两个数据进行比较,看是否满足大小关系要求,若不满足让它俩互换。
3)一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。
4)优化:若某次冒泡不存在数据交换,则说明已经达到完全有序,所以终止冒泡。
冒泡排序
// 冒泡排序,a表示数组,n表示数组大小
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; ++i) {
// 提前退出冒泡循环的标志位
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有数据交换
}
}
if (!flag) break; // 没有数据交换,提前退出
}
}
二、插入排序
1.排序原理
首先,我们将数组中的数据分为2个区间,即已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想就是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间中的元素一直有序。重复这个过程,直到未排序中元素为空,算法结束。
插入排序
// 插入排序,a表示数组,n表示数组大小
public void insertionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 1; i < n; ++i) {
int value = a[i];
int j = i - 1;
// 查找插入的位置
for (; j >= 0; --j) {
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
}
a[j+1] = value; // 插入数据
}
}
三、选择排序(Selection Sort)
选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾
选择排序
四、快速排序(Selection Sort)
1.算法原理
快排的思想是这样的:如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot(分区点)。然后遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将povit放到中间。经过这一步之后,数组p到r之间的数据就分成了3部分,前面p到q-1之间都是小于povit的,中间是povit,后面的q+1到r之间是大于povit的。根据分治、递归的处理思想,我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据,直到区间缩小为1,就说明所有的数据都有序了。
递推公式:quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
终止条件:p >= r
归并排序和快速排序
// 快速排序,A是数组,n表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数,p,r为下标
quick_sort_c(A, p, r) {
if p >= r then return
q = partition(A, p, r) // 获取分区点
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}
五、归并排序与快速排序的区别
归并和快排用的都是分治思想,递推公式和递归代码也非常相似,那它们的区别在哪里呢?
1.归并排序,是先递归调用,再进行合并,合并的时候进行数据的交换。所以它是自下而上的排序方式。何为自下而上?就是先解决子问题,再解决父问题。
2.快速排序,是先分区,在递归调用,分区的时候进行数据的交换。所以它是自上而下的排序方式。何为自上而下?就是先解决父问题,再解决子问题。