行业知识
排序算法(Java版)
目录
- 1、直接插入排序
- 2、希尔排序
- 3、直接选择排序
- 4、堆排序
- 5、冒泡排序
- 6、快速排序
- 6.1 递归实现
- 6.2 非递归实现
- 7、归并排序
- 7.1 递归实现
- 7.2 非递归实现
- 8、性能分析
今天我们学习一种算法：排序算法（本文的排序默认是从小到大顺序）！！！
1、直接插入排序
算法原理： 每次将无序序列中的第一个插入到有序序列当中，使有序序列仍为有序，第一趟排序默认第一个元素是有序的，类比于生活中的摸牌，每次将新的排插入已有的牌当中。直接插入排序的算法原理很简单，我们只需要找到每个元素该插入到哪个位置即可。
代码实现：
public void InsertSort(int[] array) { for (int i = 1; i = 0; j--) { if (array[j] > tmp) { array[j + 1] = array[j]; } else { array[j + 1] = tmp; break; } } array[j + 1] = tmp; } }代码图解：
2、希尔排序
算法原理： 希尔排序又称缩小增量排序，原理是先选定一个数作为分组的组数，将数组进行分组，接着分别对每个组进行排序，每组排序好之后，缩小分组的组数，重复上述步骤，直到组数为1。对每个组进行排序，我们使用插入排序的方法进行排序。
代码实现：
public void ShellSort(int[] array) { int gap = array.length; //分成gap组,对每一组进行插入排序 while (gap > 1) { gap /= 2; shell(array, gap); } }//对每组进行插入排序 public void shell(int[] array, int gap) { for (int i = gap; i = 0; j -= gap) { if (array[j] > tmp) { array[j + gap] = array[j]; } else { array[j + gap] = tmp; break; } } array[j + gap] = tmp; } }3、直接选择排序
算法原理： 每次待排序序列中选择最小的元素和待排序的第一个元素交换
代码实现：
public void SelectSort(int[] array) { for (int i = 0; i4、堆排序
算法原理： 堆排序是借用堆这种数据结构来实现的一种排序算法，如果升排序，建立大根堆；如果排降序，建立小根堆 。建堆之后：
1、交换0下标元素和最后一个元素的值
2、然后重新将数组进行向下调整为大根堆
重复这两个步骤，直到全部有序
代码实现：
public void HeapSort(int[] array) { //先创建大堆 createBigHeap(array); int end = array.length - 1; while (end >= 0) { //交换 int tmp = array[0]; array[0] = array[end]; array[end] = tmp; ShiftDown(array, 0, end); end--; } } public void createBigHeap(int[] array) { for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) { ShiftDown(array, parent, array.length); } } public void ShiftDown(int[] array, int parent, int end) { int child = parent * 2 + 1; while (child array[parent]) { //交换 int tmp = array[parent]; array[parent] = array[child]; array[child] = tmp; parent = child; child = parent * 2 + 1; } else { break; } } }5、冒泡排序
算法原理： 遍历数组，每次比较相邻两个元素的大小，如果大的数字在前则交换两个元素的位置，这样就完成了一趟冒泡排序，此时最大的数到了最后，然后对前n-1个数进行相同的操作，直到有序。
代码实现：
public void BubbleSort(int[] array) { for (int i = 0; i array[j + 1]) { //交换 int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; } } } }问题：如果遍历一遍数组已经有序了，就不用再继续比较下去了，因此对上面代码进行优化
优化后:
public void BubbleSort(int[] array) { boolean flg = false; for (int i = 0; i array[j + 1]) { //交换 int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; flg = true; } } if (!flg) { break; } } }6、快速排序
算法原理： 快速排序的基本思想就是：选定一个基准，通过一趟快速排序之后，能把数据分割为两部分，左边部分比基准的值小，右边的部分比基准的值大，接着再按照这个方法分别对基准左边部分和右边部分进行递归，重复这个步骤直到整个序列都有序。快速排序的最重要部分就是如何将序列分割成两部分，常见的分割方法有hoare法和挖坑法
Hoare法分割： 先选定一个基准（默认是第一个元素），定义left、right下标，left从序列最右边开始找比基准小的值（升序排序），找到之后停下来，接着让left从最左边开始找比基准大的值，找到之后停下来，将找到的这两个值交换，当left和right相遇时(left=right)，交换基准的值和left/right下标的值，这样left/right下标左边的元素全都比left/right下标的值小,右边的元素都比它大，这样就分割好了。
图解：
挖坑法：
和Hoare法的区别是：挖坑法是边找边交换，如图
6.1 递归实现
代码实现：
public void QuickSort(int[] arr) { quick(arr, 0, arr.length - 1); } public void quick(int[] arr, int left, int right) { //递归结束的条件 if (left >= right) { return; } //进行分割 int pio = partition(arr, left, right); quick(arr, 0, pio - 1); quick(arr, pio + 1, right); }hoare法分割
public int partition(int[] arr, int left, int right) { int tmp = arr[left]; int i = left; while (left = tmp) { right--; } while (left = tmp) { right--; } while (left left + 1) { stack.push(left); stack.push(pio - 1); } if (pio7、归并排序
原理： 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；归并排序的思想是：先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
7.1 递归实现
递归思路： 先将序列进行分解，直到分解为单个元素为一组，然后再进行合并。合并：开辟新的数组，新的数组存储的是合并之后且有序的子序列，再开辟的新数组的元素拷贝回原数组
public void mergeSort(int[] arr) { merge(arr, 0, arr.length - 1); } public void merge(int[] arr, int left, int right) { if (left >= right) { return; } int mid = (left + right) / 2; //分解 merge(arr, left, mid); merge(arr, mid + 1, right); //合并 mergeFun(arr, left, mid, right); } //合并 public void mergeFun(int[] arr, int left, int mid, int right) { int s1 = left; int e1 = mid; int s2 = mid + 1; int e2 = right; int k = 0; int[] tmp = new int[right - left + 1];//开辟新的数组 while (s1 if (arr[s1]
