本文记录几个基础的排序算法。排序算法分为插入排序、交换排序、选择排序等几大类。
插入排序
1. 直接插入排序 O(n2)
直接插入排序思路：将数组分为有序区和无序区，每次插入都在无序区中取一个元素，插入到有序区合适的位置。排序开始时，默认第一个元素有序，随后取第2 3 ... 个元素与有序区的元素进行对比，插入。
原始数组：
5, 2, 6, 7, 1, 3,
排序过程：
当前是第2个元素2插入：2, 5, 6, 7, 1, 3,
当前是第3个元素6插入：2, 5, 6, 7, 1, 3,
当前是第4个元素7插入：2, 5, 6, 7, 1, 3,
当前是第5个元素1插入：1, 2, 5, 6, 7, 3,
当前是第6个元素3插入：1, 2, 3, 5, 6, 7,
排序数组
1, 2, 3, 5, 6, 7,
算法如下：
public static void insertSort(int[] numbers){
int insert;
for (int i = 1; i < numbers.length; i++){
//System.out.print("当前是第" + (i+1) + "个元素" + numbers[i] +"插入：");
insert = numbers[i];
int j = i-1; //有序部分的个数
while(j>= 0 && numbers[j] > insert){ //有序部分从右到左比较，若大于插入元素，则后移
numbers[j+1] = numbers[j]; //元素后移
j--;
}
numbers[j+1] = insert; //在需要的位置插入
//fore(numbers);
}
}
2. 折半插入排序
折半插入排序的思路和直接插入排序类似：将数组分为有序区和无序区，每次插入都在无序区中取一个元素，然后通过折半查找的方式，找出插入的位置是在左半区还是在右半区，找到插入的半区后，插入到有序区合适的位置。排序开始时，默认第一个元素有序，随后取第2 3 ... 个元素与有序区的元素进行对比，插入。
public static void insertSort2(int[] numbers) {
int low, high, mid;
int insert;
for (int i = 1; i < numbers.length; i++) {
//System.out.print("当前是第" + (i+1) + "个元素" + numbers[i] +"插入：");
insert = numbers[i];
low = 0;
high = i - 1;
while (low <= high) { //在有序区中，折半查找插入的位置
mid = (low + high) / 2;
if (insert < numbers[mid]) { //插入点在左半区，设置high为中点的左边
high = mid - 1;
} else //插入点在右半区，设置high为中点的右边
low = mid + 1;
}
for (int j = i-1; j>=high+1; j--){
numbers[j + 1] = numbers[j]; //元素后移
}
numbers[high + 1] = insert; //在需要的位置插入
// fore(numbers);
}
}
3. 希尔排序 O(n1.3)
希尔排序实际上是一种分组插入的方法，思想：选定一个小于n的整数d1，作为一个增量，将距离间隔为d的元素分组，然后在组内进行直接插入排序；然后取第二个增量d2<d1，分组，组内插入排序；直到增量d=1，分组，组内直接插入排序，结束。
关于d的选取，这里建议d1 = n / 2, di+1=di / 2。
原始数组：
5, 2, 6, 7, 1, 3,
排序过程：
增量gap=3 结果：5, 1, 3, 7, 2, 6,
增量gap=1 结果：1, 2, 3, 5, 6, 7,
排序数组
1, 2, 3, 5, 6, 7,
算法：
public static void shellSort(int[] numbers) {
int gap;
gap = numbers.length / 2; //增量初始值
while (gap > 0) {
for (int i = gap; i < numbers.length; i++) { //相隔gap的元素组进行直接插入排序
int temp = numbers[i];
int j = i - gap;
while (j >= 0 && temp < numbers[j]) { //组内移动
numbers[j + gap] = numbers[j];
j = j - gap;
}
numbers[j + gap] = temp;
}
// System.out.print("增量gap=" + gap + " 结果：");
// fore(numbers);
gap = gap / 2;
}
}
交换排序
1. 冒泡排序 O(n2)
冒泡排序，也称气泡排序，对每两两相邻的关键字进行比较，使得关键字较大的排到数组的后边。一次排序后，得到的结果就将目前最大的元素放置到数组的后部，不断重复该过程，直到所有元素有序。（也有部分冒泡排序每次将最小的部分排列到数组最前端，这两者思想都是一致的）
原始数组：
5, 2, 6, 7, 1, 3,
第1趟排序：
2, 5, 6, 7, 1, 3,
2, 5, 6, 1, 7, 3,
2, 5, 6, 1, 3, 7,
第2趟排序：
2, 5, 1, 6, 3, 7,
2, 5, 1, 3, 6, 7,
第3趟排序：
2, 1, 5, 3, 6, 7,
2, 1, 3, 5, 6, 7,
第4趟排序：
1, 2, 3, 5, 6, 7,
第5趟排序：
第6趟排序：
排序数组
1, 2, 3, 5, 6, 7,
public static void bubbleSort(int[] a){
int temp;
for(int i=0;i<a.length;i++){
//System.out.println("第"+ (i+1) + "趟排序：" );
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
//fore(a); //输出
}
}
}
}
可以发现，在第5趟排序中，根本就没有交换元素，那么就表明所有元素已经按顺序排列，那么就没比较进行第六趟的比较，因此做如下优化：通过一个boolean判断是否发生交换，如果没有发生交换，则结束算法。
public static void bubbleSort2(int[] a){
int temp;
boolean exchange; //是否做交换
for(int i=0;i<a.length;i++){
exchange = false;
System.out.println("第"+ (i+1) + "趟排序：" );
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
exchange = true;
fore(a);
}
}
if (!exchange){ //本趟没有发生交换，中途结束算法
return;
}
}
}
2. 快速排序 O(nlog2n)
快速排序的思想：
- 选择一个基准base，把小于base的数值移到base左边，把大于base的数值移到右边。（此时数组中会分为小于base的左部，和大于base的右部）
- 递归将小于base和大于base的两部分重复第一步，直到递归完成。
代码实现：
public static void quickSort2(int[] numbers, int start, int end) {
int base = numbers[start];
int i = start, j = end;
int temp; //临时存储，用作交换
do {
while (numbers[i] < base && i < end) { //i从左到右找到第一个大于等于基准的值
i++;
}
while (numbers[j] > base && j > start) { //j从右到左找到第一个小于等于基准的值
j--;
}
if (i <= j) { //左右两侧都找到后，交换其位置，并将i后移，j左移
temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
i++;
j--;
}
} while (i <= j);
if (start < j) {
quickSort2(numbers, start, j); //递归小于base的左部
}
if (end > i) {
quickSort2(numbers, i, end); //递归大于base的右部
}
}
算法分析：
由于快速排序的思想分为左右两部分递归，可以快速记忆时间复杂度为O(nlog2n)
选择排序
1. 直接选择排序 O(n2)
直接选择排序思想：在当前无序区中选择最小的关键字与无序区的第一个元素进行交换，直到n-1次排序后，整个数组递增有序。
原始数组：
5, 2, 6, 7, 1, 3,
排序过程：
第1次排序：1, 2, 6, 7, 5, 3,
第2次排序：1, 2, 6, 7, 5, 3,
第3次排序：1, 2, 3, 7, 5, 6,
第4次排序：1, 2, 3, 5, 7, 6,
第5次排序：1, 2, 3, 5, 6, 7,
排序数组
1, 2, 3, 5, 6, 7,
算法：
public static void selectSort(int[] numbers) {
for (int i = 0; i < numbers.length - 1; i++) { //第i次排序
int k = i; //标记最小值的位置
for (int j = i + 1; j < numbers.length; j++) { //在无序区中选择最小的key
if (numbers[j] < numbers[k]) {
k = j;
}
}
if (k != i) { //交换
int temp = numbers[i];
numbers[i] = numbers[k];
numbers[k] = temp;
}
System.out.print("第" + (i + 1) + "次排序：");
fore(numbers);
}
}
2. 堆排序
堆排序是一种树形选择排序方法，在排序时将数组看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子节点之间的内在联系，在当前无序区中选择关键字最大的元素。
堆（完全二叉树）的定义n个关键字的序列K1, K2... Kn，当且仅当该序列满足以下属性：
- Ki <= K2i且 Ki <= K2i+1 ：小根堆
或者： - Ki >= K2i且 Ki >= K2i+1 ：大根堆
算法思想：堆排序的关键在于构造初始堆，假设完全二叉树的某一个节点i，它的左右子树都是堆，这时就需要将R[i]和R[2i]、R[2i + 1]之间的最大者进行比较，如果R[i]较小，那么就将其与较大的孩子进行交换，这个交换过程中，可能会导致下一级的堆被破坏，因此需要用上述的方法递归构造下一级堆。
调整堆算法：
/**
* 调整堆算法
*
* @param numbers 数组
* @param low 要调整的节点
* @param high 最后一个节点的位置
*/
public static void sift(int[] numbers, int low, int high) {
int i = low, j = 2 * i; //j是i的左节点
int temp = numbers[i];
while (j <= high) {
if (j < high && numbers[j] < numbers[j + 1]) { //如果右孩子较大，则将j指向右孩子
j++;
}
if (temp < numbers[j]) {
numbers[i] = numbers[j]; //将numbers[j]调整到双亲节点上
i = j;
j = 2 * i; //修改i、j的值
} else
break;
}
numbers[i] = temp; //被筛选的节点（要调整的节点）放置到最终位置
}
在初始堆构造好后，根节点是最大的关键字节点，将其放置到序列的最后（和最后一个叶子节点交换），由于最大元素已经归为，待排序的元素会减少一个，根节点也改变了，就需要重新调用sift算法调整堆；然后重复上述步骤，直到完全二叉树只剩最后一个根为止。
原始数组：
5, 2, 6, 7, 1, 3,
排序过程：
调整堆：5, 2, 6, 7, 1, 3,
调整堆：5, 7, 6, 2, 1, 3,
调整堆：7, 6, 5, 2, 1, 3,
初始堆完成：7, 6, 5, 2, 1, 3,
调整堆：6, 5, 3, 2, 1, 7,
调整堆：5, 3, 1, 2, 6, 7,
调整堆：3, 2, 1, 5, 6, 7,
调整堆：2, 1, 3, 5, 6, 7,
调整堆：1, 2, 3, 5, 6, 7,
排序数组
1, 2, 3, 5, 6, 7,
/**
* 堆排序
*
* @param numbers 数组
*/
public static void HeapSort(int[] numbers) {
int temp;
int n = numbers.length-1;
for (int i = n / 2; i >= 0; i--) { //构造初始堆
sift(numbers, i, n);
}
System.out.print("初始堆完成：");
fore(numbers);
for (int i = n; i >= 1; i--) {
temp = numbers[0]; //将最后一个元素和当前区内的第一个节点交换
numbers[0] = numbers[i];
numbers[i] = temp;
sift(numbers, 0, i - 1); //得到i-1个节点的堆
}
}
网友评论