几种常见排序算法
算法：几种常见排序算法
文章目录
说明：以下代码实现都是按照从小到大排训实现的。
一，冒泡排序
1. 百度百科：
冒泡排序（Bubble Sort）：是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
2. 代码示例：
package leetcode.editor.utils;
/** * @author 张文军 * @Description: * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/9/300:32 */
public class BubbleSort {
int[] arr;
public BubbleSort(int[] arr) {
this.arr = arr;
}
public int[] sort() {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
}
3. 优化：
package leetcode.editor.utils;
import java.util.Arrays;
/** * @author 张文军 * @Description: * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/9/300:32 */
public class BubbleSort {
int[] arr;
public BubbleSort(int[] arr) {
this.arr = arr;
}
public int[] sort() {
/** * isSwap 判断是否进行了交换 如果在一趟排序过程中一次都没有交换，说明已经有序。 */
boolean isSwap = true;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
isSwap = false;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if (isSwap) {
break;
} else {
isSwap = true;
}
System.out.println("第 " + (i+1) + " 次排训后的结果为：" + Arrays.toString(arr));
}
return arr;
}
public static void main(String[] args) {
int[] sort = new BubbleSort(new int[]{1, 23, 56, 78, -12}).sort();
System.out.println("排训前的结果:"+Arrays.toString(new int[]{1, 23, 56, 78, -12}));
System.out.println("排训后的结果:"+Arrays.toString(sort));
}
}
4. 结果：
说明：
(1) 一共进行 数组的大小-1 次 大的循环
(2)每一趟排序的次数在逐渐的减少
(3) 如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。这个就是优化
二，选择排序：
1. 百度百科：
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
2. 实现过程：
对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量 minIndex来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量 minIndex记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让最后一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推
3. 代码示例：
package leetcode.editor.utils;
import java.util.Arrays;
/** * @author 张文军 * @Description: * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/9/302:07 */
public class SelectionSort {
int[] arr;
public SelectionSort(int[] arr) {
this.arr = arr;
}
public int[] sort() {
for (int i = 0; i < arr.length - 1; i++) {
/* 每一趟排训中最小值的下标 */
int minIndex = i;
int min = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) {
minIndex = j;
min = arr[j];
}
}
int temp;
if (minIndex != i) {
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
System.out.println("第 " + (i+1) + " 次排训后的结果为：" + Arrays.toString(arr));
}
return arr;
}
public static void main(String[] args) {
int[] sort = new SelectionSort(new int[]{1, 23, 56, 78, -12}).sort();
System.out.println("排训前的结果:"+Arrays.toString(new int[]{1, 23, 56, 78, -12}));
System.out.println("排训后的结果:"+Arrays.toString(sort));
}
}
4. 测试结果：
说明：
选择排序一共有 数组大小 - 1 轮排序
每1轮排序，又是一个循环, 循环的规则(代码)
2.1先假定当前这个数是最小数
2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标
2.3 当遍历到数组的最后时，就得到本轮最小数和下标
2.4 交换 [代码中 ]
三、直接插入排序
1. 百度百科：
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
2. 实现过程：
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
3. 代码示例：
package leetcode.editor.utils;
import java.util.Arrays;
/** * @author 张文军 * @Description:插入排序 * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/9/3017:18 */
public class InsertionSort {
int[] arr;
public InsertionSort(int[] arr) {
this.arr = arr;
}
public int[] sort() {
for (int i = 1; i < arr.length; i++) {
/** * 要插入的元素，若直接用a[i]表示，a[j+1]操作会更改a[i]的值 */
int toInsertNum = arr[i];
/** * 表示从已排好序的数组的最右边开始比较 */
int j = i - 1;
while (j >= 0 && arr[j] > toInsertNum) {
/** * 若插入的元素小，则将被比较的元素后移一位 */
arr[j + 1] = arr[j];
j--;
}
/** * 此时的a[j]代表着被插入元素左边相邻的那个元素，需要将待插入元素插入到它的前一个位置 */
arr[j + 1] = toInsertNum;
System.out.println("第 " + (i) + " 次排训后的结果为：" + Arrays.toString(arr));
}
return arr;
}
public static void main(String[] args) {
int[] sort = new InsertionSort(new int[]{1, 123, 56, 78, -12}).sort();
System.out.println("排训前的结果:"+Arrays.toString(new int[]{1, 123, 56, 78, -12}));
System.out.println("排训后的结果:"+Arrays.toString(sort));
}
}
4. 测试结果：
说明：
把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
四、希尔排序 ( 分组排序 , 又名缩小增量排序 )
1. 概述：
简单明显存在问题：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。希尔排序是对直接插入排训的优化。
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
2. 百度百科：
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
3. 基本思想：
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
4. 实现：
实现方法一：交换法
1) 实现代码：
package leetcode.editor.utils;
import java.util.Arrays;
/** * @author 张文军 * @Description:希尔排序 * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/10/20:07 */
public class ShellSort {
private int arr[];
public ShellSort(int[] arr) {
this.arr = arr;
}
public int[] sort() {
int count = 0;
int temp;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
for (int j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
++count;
System.out.println("第" + count + "轮排序后 :" + Arrays.toString(arr));
}
return arr;
}
public static void main(String[] args) {
System.out.println("排训前的结果:" + Arrays.toString(new int[]{1, 123, 56, 78, -12, 0}));
int[] sort = new ShellSort(new int[]{1, 123, 56, 78, -12, 0}).sort();
System.out.println("排训后的结果:" + Arrays.toString(sort));
}
}
2) 测试结果：
实现方法二：移步法(插入法)（最佳）
1）实现代码：
package leetcode.editor.utils;
import java.util.Arrays;
/** * @author 张文军 * @Description:希尔排序 * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/10/20:07 */
public class ShellSort {
private int arr[];
public ShellSort(int[] arr) {
this.arr = arr;
}
public int[] sort() {
int count = 0;
/** * 增量gap ：逐步缩小增量 */
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
/** * 表示从已排好序的数组的最右边开始比较 */
int j = i - gap;
/** * 要插入的元素，若直接用a[i]表示，a[j+gap]操作会更改a[i]的值 */
int toInsertNum = arr[i];
while (j >= 0 && arr[j] > toInsertNum) {
/** * 若插入的元素小，则将被比较的元素后移一位 */
arr[j + gap] = arr[j];
/** * 指针向前移动 */
j -= gap;
}
/** * 此时的a[j]代表着被插入元素左边相邻的那个元素，需要将待插入元素插入到它的前gap个位置 */
arr[j + gap] = toInsertNum;
}
System.out.println("第 " + (++count) + " 次排训后的结果为：" + Arrays.toString(arr));
}
return arr;
}
public static void main(String[] args) {
System.out.println("排训前的结果:" + Arrays.toString(new int[]{1, 123, 56, 78, -12, 0}));
int[] sort = new ShellSort(new int[]{1, 123, 56, 78, -12, 0}).sort();
System.out.println("排训后的结果:" + Arrays.toString(sort));
}
}
说明：
个人理解希尔排序：就是将数据分成若干组（减少直接插入法时移动的次数），在本组内用插入排序法，将较小的数调整到后面（前面）。。。直到分组数为1时，此时经过上述步骤，数据基本已经有序，这时再进行插入排序，可得结果。（大大提升了无序数的排序速度）。
