冒泡排序、选择排序、插入排序、快速排序

一、冒泡排序

冒泡排序的算法思路：

每一轮都是数组元素之间两两相互比较，把大的元素往后面放，经过一轮比较和交换后，就把最大的元素放在了最后面。往复进行上述步骤，这样就把数组按由小到大的顺序排列了。如下图所示： 这段代码是将冒泡排序的步骤分开进行的：

//第一轮： for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) { //交换位置 int t = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = t; } } System.out.println(Arrays.toString(arr)); //第二轮 for (int i = 0; i < arr.length - 1 - 1; i++) { if (arr[i] > arr[i + 1]) { //交换位置 int t = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = t; } } System.out.println(Arrays.toString(arr)); //第三轮： for (int i = 0; i < arr.length - 1 - 1 - 1; i++) { if (arr[i] > arr[i + 1]) { //交换位置 int t = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = t; } } System.out.println(Arrays.toString(arr)); //第四轮： for (int i = 0; i < arr.length - 1 - 1 - 1 - 1; i++) { if (arr[i] > arr[i + 1]) { //交换位置 int t = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = t; } } System.out.println(Arrays.toString(arr));

将上述分开的步骤进行归纳和总结后，得到如下代码：

package cm.java.about_day13; import java.util.Arrays;//导入了Arrays工具包 public class BubbleSort { public static void main(String[] args) { int[] arr = {11, 77, 9, -8, 45, -3, 88,-96, 0}; 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 tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } System.out.println(Arrays.toString(arr));//这里使用了关于数组的toString()方法 } } 运行结果就是将上述数组元素按由小到大的顺序排列了。

二、选择排序

选择排序的算法思路：

每一轮取一个元素和后面所有的元素逐个比较，将小的元素往前放，经过一轮比较和交换，最小的元素会出现在最前面。往复进行上述步骤，这样就把数组按由小到大的顺序排列了。如下图所示： 这段代码是将选择排序的步骤分开进行的：

//第一轮： int index = 0; for (int i = 1+index; i < arr.length; i++) { if(arr[index] > arr[i]){ //交换位置 int t = arr[index]; arr[index] = arr[i]; arr[i] = t; } } System.out.println(Arrays.toString(arr)); //第二轮: index = 1; for (int i = 1+index; i < arr.length; i++) { if (arr[index] > arr[i]) { //交换位置 int t = arr[index]; arr[index] = arr[i]; arr[i] = t; } } System.out.println(Arrays.toString(arr)); //第三轮： index = 2; for (int i = 1 + index; i < arr.length; i++) { if (arr[index] > arr[i]) { //交换位置 int t = arr[index]; arr[index] = arr[i]; arr[i] = t; } } System.out.println(Arrays.toString(arr)); //第四轮： index = 3; for (int i = 1 + index; i < arr.length; i++) { if (arr[index] > arr[i]) { //交换位置 int t = arr[index]; arr[index] = arr[i]; arr[i] = t; } } System.out.println(Arrays.toString(arr)); } }

将上述分开的步骤进行归纳和总结后，得到如下代码：

//我将选择排序抽成了一个方法； private static void selectSort(int[] arr) {//选择排序 for(int i = 0; i < arr.length - 1; i++) { for(int j = i + 1; j < arr.length; j++) { if(arr[i] > arr[j]) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } } System.out.println(Arrays.toString(arr)); }

三、插入排序

插入排序的算法思路:

直接插入排序,是一种最简单的排序方法.它的基本操作是：将一个记录插入到一个长度为m 的有序表中,使之仍保持

有序,从而得到一个新的长度为m+1的有序列表.假设有一组元素{k1,k2…,kn},排序开始就认为k1是一个有序序列,让

k2插入上述表长为1的有序序列,使之成为一个表长为2的有序序列,然后让k3插入上述表长为2的有序序列,使之成为

一个表长为3的有序序列,以此类推,最后让kn插入表长为n-1的有序序列,得到一个表长为n的有序序列.

例如:

49,38,65,97,76,13,27 原始数据

[49],38,65,97,76,13,27 从1索引开始插入

[38,49], ,65,97,76,13,27

[38,49,65] 97,76,13,27

[38,49,65,97] 76,13,27

[38,49,65,76,97]13,27

[13,27,38,49,65,76,97],27

[13,27,38,49,65,76,97]

package cm.java.about_day13; import java.util.Arrays; public class InsertSort { public static void main(String[] args) { int[] arr = {11, 77, 9, -8, 45, -3, 88,-96, 0}; for(int i = 1; i < arr.length; i++) { for(int j = i; j > 0; j--) { if(arr[j] < arr[j -1]) { int tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp; } } } System.out.println(Arrays.toString(arr)); } }

四、快速排序

快速排序的算法思想：

1.分治法：比大小，再分区

(1)从数组中取出一个数，作为基准数。

(2)分区：将比这个数大或等于的数全放到他的右边，小于他的数

全放到他的左边。

(3)再对左右区间重复第二步，直到各区间只有一个数。

2.挖坑填数

(1)将基准数挖出形成第一个坑。

(2)由后向前找比他小的数，找到后挖出此数填到前一个坑中。

(3)由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。

(4)再重复执行2，3两步骤。

例如对 5、3、9、1、6、7、2 进行排序：

这里我就只走一轮填坑：

首先以下标为0的元素5作为基准数并挖坑，然后从数的最后面开始找比5小的数，找到了元素2，于是就将2填进坑里（同时j下标要同步进行变换），并在元素2处挖坑，元素值改为5；然后再从坑前面找比5大的数，找到了元素9，于是就将9填进坑里（同时i下标要同步进行变换），并在元素9处挖坑，元素值改为5；然后再从坑后面找比5小的数，找到了元素1，于是就将1填进坑里（同时j下标要同步进行变换），并在元素1处挖坑，元素值改为5；当你会发现i 不小于 j 时，此时就将小于基准数的数都放在了基准数的前面，同时也将大于基准数的数都放在了基准数的后面，经过一轮挖坑填数后，得到2、3、1、5、6、7、9；然后继续照此方法进行就行。

//这里将快排和得到基准数的下标写成了方法 public class QuickSort { //start 默认是0 //end 是数组长度-1 public void quickSort(int[] arr, int start, int end) { if (start < end) { //获取分区索引 int index = getIndex(arr, start, end); //对左右两个分区 再进行同样的步骤 ，即是递归调用 quickSort(arr, start, index - 1);//左半部分 quickSort(arr, index + 1, end);//右半部分 } } private int getIndex(int[] arr, int start, int end) { int i = start; int j = end; //定义基准数(也就是挖坑) int x = arr[i]; //循环 while (i < j) { //从右往左比较 while (i < j && arr[j] >= x) { j--; } //从右往左找到比基准数小的数了后，填坑 if (i < j) { //把这个数填到上一个坑位 arr[i] = arr[j]; i++;//下标后移 } //从左往右找 while (i < j && arr[i] < x) { i++; } // 找比基准数大的数，找到后填坑 if (i < j) { arr[j] = arr[i]; j--;//下标前移 } } //当上面的循环结束后把基准数填到最后一个坑位，也就以基准数为界，分成了左右两部分 arr[i] = x; //把基准数填进去 return i; //返回基准数所在位置的索引 } }