转自:https://zhuanlan.zhihu.com/p/80043870
1、冒泡排序(Bubble Sort)
冒泡排序:对每一对相邻的元素比较大小,若顺序错误则交换顺序(正确的顺序由排序方向决定,我们假定数组元素应该从小到大排序);这样从头到尾操作一遍,最大的元素将会在最后一个(操作的一组元素的最后一个);对前面未确认顺序的重复以上操作,直到没有元素可操作即排序完成。
1.1 算法描述:
(1)对一组元素,将相邻两个元素比较大小,如果顺序错误则交换顺序;
(2)对每一对相邻元素作同样的操作,从每一组开头一对到最后一对元素,这样每一组元素最后一个元素会是最大;
(3)循环n次(n为数组长度),每次选择前n - 1 - i个(i为第几次循环)元素重复(1)、(2)步骤;
1.2 代码实现:
public static int[] bubbleSort(int[] arr){
int len = arr.length;
if (len == 0) return arr;
for (int i = 0; i < len; i++){
for (int j = 0; j < len - 1 - i; j++){
if (arr[j+1] < arr[j]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
2、选择排序(Selection Sort)
选择排序:是一种简单直接的排序算法,它的工作原理是:遍历未排序元素,将最小值(或者最大值)和遍历的第一个元素交换位置;然后继续在剩余未排序的元素中重复以上操作,直到将所有元素排序完成。
2.1 算法描述:
(1)初始状态:无序区为R[1..n],有序区为空;
(2)第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
(3)n-1趟结束,数组有序化了。
2.2 代码实现:
public static int[] selectorSort(int[] arr){
int len = arr.length;
if (len == 0) return arr;
for (int i = 0; i < len-1; i++){
int minIndex = i;
//遍历出每趟的最小值
for (int j = i+1; j < len; j++){
if (arr[j] < arr[minIndex]){
minIndex = j;
}
}
//把最小值与每趟第一个元素交换位置
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
3、插入排序(Insertion Sort)
插入排序:一种简单直观的排序算法。它的工作原理是:通过构建有序序列,依次取未排序序列元素,在有序序列后面从后往前扫描,找到相应位置插入,插入位置后面的元素需要依次外后移动,为新元素提供位置。
3.1 算法描述
(1)从第一个元素开始,可以认为是已经排好序了
(2)取出下一个新元素,依次从后往前扫描;
(3)如果扫描到的元素比新元素大,则将扫描到的元素依次往后移动一个位置;
(4)重复步骤(3)直到扫描到的元素小于等于新元素,则将新元素插入该位置之后;
(5)重复步骤(2)~(4),直到最后一个元素被插入正确的位置。
3.2 代码实现
public static int[] insertionSort(int[] arr){
int len = arr.length;
if (len == 0) return arr;
for (int i = 0;i < len -1; i++){
int curr = arr[i+1]; //这是要插入的新元素
int preIndex = i;
//从后往前扫描有序序列,如果新元素小于等于扫描到的元素,则将被扫描的元素依次后移一个位置,注意不要下标不要越界
while (preIndex >= 0 && arr[preIndex] > curr){
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
//上面的while循环跳出则表示当前preIndex的元素比新元素小或者已经越界,应该把新元素插入preIndex+1位置
arr[preIndex+1] = curr;
}
return arr;
}
4、希尔排序(Shell Sort)
希尔排序:是插入排序的改良版本,又叫缩小增量排序。希尔排序是把记录按下表的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
4.1 算法描述:
在此我们选择增量为gap = length / 2,继续缩小增量gap = gap / 2直到 gap == 1,我们用一个序列来表示这些增量{len/2, (len/2)/2, ....,1} 这种增量序列的选择和证明是一种数学难题,在此选择的增量是比较常见的,也是希尔建议的称之为希尔增量。
先将整个待排序的序列分割为若干个子序列分别进行插入排序,具体如下
(1)选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
(2)按增量序列个数k,对序列进行k 趟排序;
(3)每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
4.2 代码实现:
public static int[] shellSort(int[] arr){
int len = arr.length;
if (len == 0) return arr;
int gap = len / 2; //增量初始值
while (gap > 0){
for (int i = gap; i < len; i++){
//对每个分组进行插入排序
int curr = arr[i];
int preIndex = i - gap;
while (preIndex >= 0 && arr[preIndex] > curr){
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = curr;
}
gap = gap / 2; //缩小增量,重新分组进行插入排序
}
//gap==1时,将所有序列分为一组进行插入排序
return arr;
}
5、归并排序(Merge Sort)
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
5.1 算法描述:
(1)把长度为n的输入序列分成两个长度为n/2的子序列;
(2)对这两个子序列分别采用归并排序;
(3)将两个排序好的子序列合并成一个最终的排序序列。
5.2 代码实现:
public static int[] mergeSort(int[] arr){
if (arr.length < 2) return arr;
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0 , mid);
int[] right = Arrays.copyOfRange(arr, mid , arr.length);
return merge(mergeSort(left), mergeSort(right));
}
/**
* 将两个有序序列 组合成一个新的有序序列
*/
private static int[] merge(int[] left, int[] right){
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++){
if (i < left.length && j < right.length){
if (left[i] <= right[j]) {
result[index] = left[i++];
} else if (left[i] > right[j]) {
result[index] = right[j++];
}
} else {
if (i >= left.length) result[index] = right[j++];
else if (j >= right.length) result[index] = left[i++];
}
}
return result;
}
未完待续。。。
网友评论