排序算法Java实现

本文会通过Java语言实现：冒泡排序，插入排序，选择排序，归并排序，快速排序，桶排序，计数排序，基数排序，希尔排序

1 分析排序算法

1.1 执行效率

• 最好的情况，最坏的情况，平均情况时间复杂度
• 时间复杂度的系数，常数，低阶
• 比较次数和交换次数

1.2 算法的内存消耗

算法的内存消耗我们可以通过空间复杂度来度量。

原地排序算法，就是特指空间复杂度是O(1)的排序算法。

1.3 排序算法的稳定性

如果序列中有值相等的元素， 经过排序之后，相等元素之间原有的先后顺序不变化。

2 冒泡排序

稳定排序算法，原地排序算法，时间复杂度：O(n^2)

冒泡排序操作相邻的两个数据，每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系。每次冒泡都能选出最大的或者最小的值。

 /** * 冒泡排序 * @param arr * @return */ public static int[] bubbleSort(int[] arr) { if (arr == null || arr.length == 0) { return null; } int n = arr.length; // 总共需要循环n次 每次通过冒泡 得到最大的 for (int i = 0; i < n; i++) { // 因为上一次已经确定了最大的，所以需要遍历的数据就是(n-1)-i boolean flag = true; for (int j = 0; j < (n - 1) - i ; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag = false; } } // 因为冒泡 如果这次冒泡没有数据没有交换所以数据已经有序了，可以提前退出 if (flag) { break; } } return arr; } 

3 插入排序

稳定排序算法，原地排序算法，时间复杂度O(n^2)

根据，把位置的元素，插入在有序的集合中，插入的时候根据元素位置大小。

首先：讲数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素就是数组的第一个元素。

/** * 插入排序 * @param arr * @return */ public static int [] insertSort(int [] arr){ if (arr==null||arr.length==0) { return null; } int n = arr.length; // n从一1开始表示a[0]属于有序序列 for (int i = 1; i < n; i++) { // 当前需要比较的数字 int value = arr[i]; // 需要比较的次数 int j = i-1; // 查找插入的位置 for (; j>=0; j--) { if (arr[j]>value) { // 数据移动 arr[j+1] = arr[j]; }else { // 插入排序前面是有序序列，所有不需要移动数据的时候，直接跳出比较下个数字 break; } } // 插入数据 arr[j+1] = value; } return arr; } 

4 选择排序

不是稳定排序算法，原地排序算法，时间复杂度是O(n^2)

每次会从未排序区间中找到最小元素，将其放到已排序区间的末尾

 /** * 选择排序 * @param arr * @return */ public static int [] selectionSort(int [] arr){ if (arr==null||arr.length==0) { return null; } int n = arr.length; int temp = 0; int minKey = 0; // 刚开始没有有序区间，所以从0开始 for (int i = 0; i < n; i++) { minKey = i; // 寻找无序区间最小的元素 for (int j = i+1; j < n; j++) { if (arr[j]<arr[minKey]) { minKey = j; } } // 交换位置 temp = arr[i]; arr[i] = arr[minKey]; arr[minKey] = temp; } return arr; } 

未完，待续