排序算法

冒泡排序

基本思想 通过对待 排序序列从前向后(从下标较小的元素开始),依次比较 相邻元素的值，若发现逆序则交换，使值较大 的元素逐渐从前移向后部，就象水底下的气泡一样逐渐 向上冒。

规则

一共进行数组大小-1次外层循环；每一趟排序的次数在逐渐的减少；如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序

代码实现（未优化）

public static void bubbleSort(int[] arr){ //外层循环进行数组长度-1次 for (int j = 0; j < arr.length-1; j++) { //内层循环每一次排序过后，都会少一次 for (int i = 0; i < arr.length-1-j; i++) { if (arr[i]>arr[i+1]){ int temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; } } } }

时间复杂度： 空间复杂度：

优化冒泡排序 在排序的过程中，各元素不断有序，如果一趟下来没有进行过交换，就说明序列有序，因此可以在排序过程中设置一个结束标志stop判断元素是否进行过交换，从而减少不必要的比较。

public static void bubbleSort1(int[] arr){ //外层循环 for (int i = 0; i < arr.length-1; i++) { //设置一个临时变量，查看每一趟是否进行了交换 boolean stop=false; for (int j = 0; j < arr.length-1-i; j++) { if (arr[j]>arr[j+1]){ int temp=arr[j+1]; arr[j+1]=arr[j]; arr[j]=temp; stop=true; } } //没有交换，就结束排序 if (!stop) { break; } } }

时间复杂度： 空间复杂度：

选择排序

基本思想 第一次从arr[0]_{arr[n-1]中选取最小值，与arr[0]进行交换；第二次从arr[1]}arr[n-1]中选取最小值，与arr[1]进行交换；第三次从arr[2]_{arr[n-1]中选取最小值，与arr[2]进行交换；第i次从arr[i-1]}arr[n-1]中选取最小值，与arr[i-1]进行交换，···，第n-1次从a[n-2]~a[n-1]中选取最小值，与a[n-2]进行交换，总共进行n-1次，得到一个从小到大排序的序列。排序过程 原始数组：4，2，8，5 第一趟排序：2，4，8，5 第二趟排序：2，4，8，5 第三趟排序：2，4，5，8规则 选择排序一共有数组大小-1次排序每一次排序又是一个循环，循环规则如下 先假定当前未排序序列第一个数的下标为最小数下标然后和后面的每个数进行比较，如果发现有比当前最小数更小的数，那么就更新当前最小数的下标当遍历到数组末尾时，就得到本轮最小数的下标交换 代码实现public static void selectSort(int[] arr){ for (int i = 0; i <arr.length-1 ; i++) { //假定最小数下标 int minIndex=i; //每一趟寻找未排序序列寻找最小数下标 for (int j = i+1; j <arr.length-1 ; j++) { if (arr[minIndex]>arr[j]) { minIndex=j; } } //交换 if (minIndex!=i) { int temp=arr[minIndex]; arr[minIndex]=arr[i]; arr[i]=temp; } } System.out.println(Arrays.toString(arr)); } 时间复杂度： 空间复杂度：

插入排序

基本思想 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它和有序表中的元素依次做比较，将它插入到有序表中的适当位置，使之称为有序表中的新元素。排序过程 第一趟//第1趟代码实现 //确定待插入的数字 int insertValue = arr[1]; //确定待插入的位置：待插入数字的前一个位置 int insertIndex = 1 - 1; //寻找合适的插入位置，insertIndex>=0：防止数组下标越界；insertValue<arr[insertIndex]：寻找比insertValue更小的数 while (insertIndex >= 0 && insertValue < arr[insertIndex]) { //将比待插入数insertValue大的数字往后移 arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } //如果寻找到合适的位置以后，执行插入操作，此时，insertValue>arr[insertIndex]或者insertIndex=-1 arr[insertIndex + 1] = insertValue; System.out.println("第一趟排序的结果：" + Arrays.toString(arr)); 第二趟//第2趟排序代码实现 //确定待排序的数字 insertValue = arr[2]; //确定待插入的位置：待排序数字的前一个位置 insertIndex = 2 - 1; //寻找合适的插入位置 while (insertIndex >= 0 && arr[insertIndex] > insertValue) { //将比indexValue大的数字往后移动 arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } //寻找到合适的位置 arr[insertIndex + 1] = insertValue; System.out.println("第二趟排序的结果：" + Arrays.toString(arr)); 第三趟//第3趟排序代码实现 //确定待排序的数字 insertValue = arr[3]; //确定待插入的位置：待排序数字的前一个位置 insertIndex = 3 - 1; //寻找合适的插入位置 while (insertIndex >= 0 && arr[insertIndex] > insertValue) { //将比indexValue大的数字往后移动 arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } //寻找到合适的位置 arr[insertIndex + 1] = insertValue; System.out.println("第二趟排序的结果：" + Arrays.toString(arr)); 以此类推，第n-1趟(n个数，执行n-1次排序)//第3趟排序代码实现 //确定待排序的数字 insertValue = arr[n-1]; //确定待插入的位置：待排序数字的前一个位置 insertIndex = n-1-1; //寻找合适的插入位置 while (insertIndex >= 0 && arr[insertIndex] > insertValue) { //将比indexValue大的数字往后移动 arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } //寻找到合适的位置 arr[insertIndex + 1] = insertValue; System.out.println("第二趟排序的结果：" + Arrays.toString(arr)); 算法实现public static void insertSort(int[] arr) { for (int i = 1; i <arr.length ; i++) { //确定待插入的数字 int insertValue = arr[i]; //确定待插入的位置：待插入数字的前一个位置 int insertIndex = i-1; //寻找合适的插入位置，insertIndex>=0：防止数组下标越界；insertValue<arr[insertIndex]：寻找比insertValue更小的数 while (insertIndex >= 0 && insertValue < arr[insertIndex]) { //将比待插入数insertValue大的数字往后移 arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } //如果寻找到合适的位置以后，执行插入操作，此时，insertValue>arr[insertIndex]或者insertIndex=-1 arr[insertIndex + 1] = insertValue; System.out.println("第"+i+"趟排序的结果：" + Arrays.toString(arr)); } }