排序(Sort)

1. 排序的概念及引用

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持
不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳
定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序

1.2排序的运用

1.3常见的排序算法

2.常见排序算法的实现

2.1直接插入排序

代码思想：直接插入排序是稳定的排序，首先我们默认拿到第一个数字就是有序的，从第二个数字开始，定义一个变量tmp，首先将第二个数字放进tmp中，定义j循环，初始条件为i-1。让j下标的元素和tmp作比较，如果j比tmp的元素大，就将他向后移一下，然后j–，当内层循环结束之后将tmp放到j+1的位置。

稳定性：稳定的
时间复杂度：最坏情况下：O(n²) 最好情况下：O(n)

空间复杂度：O(1)

public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int tmp=array[i];int j=i-1;for (; j >=0; j--) {//这里加不加等号  和稳定有关系// 但是：本身就是一个稳定的排序 可以实现为不稳定的排序// 但是 本身就是一个不稳定的排序 是不可能变成一个稳定的排序的if (array[j]>tmp){array[j+1]=array[j];}else {break;}}array[j+1]=tmp;}}

2.2选择排序

代码思想：首先定义一个minIndex，来 记录最小元素的下标。因为是第一个元素，只有他自己，最小下标就存放第一个元素的下标。定义for循环从0开始，再嵌套一个for循环从i+1的位置开始，当j下标的元素小于minIndex下标的元素，将minIndex更新为j，当内循环走完之后，交换i下标位置的元素和minIndex位置元素。

代码实现：

private static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}/*** 选择排序：* 时间复杂度：O(n^2)* 空间复杂度：O(1)* 稳定性：不稳定的排序* @param array*/public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i+1; j < array.length; j++) {if(array[j] < array[minIndex]) {minIndex = j;}}swap(array,i,minIndex);}}

稳定性：不稳定的排序
时间复杂度：O(n²)
空间复杂度: O(1)

2.3堆排序

代码思想：首先我们要建立大根堆(数据从小到大排序就用大根堆)。设置end变量，让他从最后一个元素开始，当end>0，就将根节点元素和end位置元素进行交换，交换完接着向下调整让他依然保持着大根堆，end–到最后

向下调整：向下调整一般是从最后一棵子树开始调整。首先我们判断是不是有左孩子，利用公式

如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

计算后得知有左孩子，当左孩子小于数组长度的时候，我们需要判断左孩子的元素是否大于右孩子的元素，取出最大值将他的下标赋值给child。注意child下标不能越界

前面判断之后我们还需要判断child下标的元素是否大于parent下标的元素，如果大于就交换，并且让parent走到child的位置，child走到2*parent+1的位置再次进行比较

代码：

 private static void createHeap(int[] array) {for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {siftDown(array,parent,array.length);//alt+enter}}private static void siftDown(int[] array,int parent, int length) {int child = 2*parent + 1;while (child < length) {if(child+1 < length && array[child] < array[child+1]) {child++;}if(array[child] > array[parent]) {swap(array,child,parent);parent = child;child = 2*parent+1;}else {break;}}}/*** 时间复杂度：O(N*logN)* 空间复杂度：O(1)* 稳定性：不稳定的排序* @param array*/public static void heapSort(int[] array) {createHeap(array);int end = array.length-1;while (end > 0) {swap(array,0,end);siftDown(array,0,end);end--;}}

时间复杂度：O(N*logN)（以2为底）
空间复杂度：O(1)
稳定性：不稳定的排序

2.4冒泡排序

 /*** 时间复杂度：O(N^2)*    如果加了优化：最好情况下 可以达到O(n)* 空间复杂度：O(1)* 稳定性：稳定的排序** 优化：*   每一趟都需要判断 上一趟 有没有交换* @param array*/public static void bubbleSort(int[] array) {//i代表的是趟数for (int i = 0; i < array.length-1; i++) {boolean flg = false;//j来比较 每个数据的大小for (int j = 0; j < array.length-1-i; j++) {if(array[j] > array[j+1]) {swap(array,j,j+1);flg = true;}}if(!flg) {break;}}}

• 时间复杂度：O(N^2)
  • 如果加了优化：最好情况下 可以达到O(n)
  • 空间复杂度：O(1)
  • 稳定性：稳定的排序

2.5快速排序

/*** 快速排序-》* 时间复杂度：*       最好的情况下：O(N*logN)*       最坏情况下：O(N^2) 逆序/有序* 空间复杂度：*       最好的情况下：O(logN)*       最坏情况下：O(N) 逆序/有序* 稳定性：不稳定* @param array*/public static void quickSort(int[] array) {quick(array,0,array.length-1);}/*** 求中位数的下标* @param array* @param left* @param right* @return*/private static int middleNum(int[] array,int left,int right) {int mid = (left+right)/2;if(array[left] < array[right]) {if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {return right;}else {return mid;}}else {//array[left] > array[right]if(array[mid] < array[right]) {return right;}else if(array[mid] > array[left]) {return left;}else {return mid;}}}

时间复杂度：
最好的情况下：O(N*logN)（以2为底）
最坏情况下：O(N^2) 逆序/有序

空间复杂度：
最好的情况下：O(logN)
最坏情况下：O(N) 逆序/有序

稳定性：不稳定

2.6归并排序

/*** 时间复杂度：O(N*logN)* 空间复杂度：O(logN)* 稳定性：稳定的排序* 目前为止3个稳定的排序：直接插入排序、冒泡排序、归并排序* @param array*/public static void mergeSort(int[] array) {mergeSortFun(array,0,array.length-1);}private static void mergeSortFun(int[] array,int start,int end) {if(start >= end) {return;}int mid = (start+end)/2;mergeSortFun(array,start,mid);mergeSortFun(array,mid+1,end);//合并merge(array,start,mid,end);}private static void merge(int[] array, int left, int mid, int right) {int s1 = left;//可以不定义，这样写为了好理解int e1 = mid;//可以不定义，这样写为了好理解int s2 = mid+1;int e2 = right;//可以不定义，这样写为了好理解//定义一个新的数组int[] tmpArr = new int[right-left+1];int k = 0;//tmpArr数组的下标//同时满足 证明两个归并段 都有数据while (s1 <= e1 && s2 <= e2) {if(array[s1] <= array[s2]) {tmpArr[k++] = array[s1++];}else {tmpArr[k++] = array[s2++];}}while (s1 <= e1) {tmpArr[k++] = array[s1++];}while (s2 <= e2) {tmpArr[k++] = array[s2++];}//把排好序的数据 拷贝回原来的数组array当中for (int i = 0; i < tmpArr.length; i++) {array[i+left] = tmpArr[i];}}

时间复杂度：O(N*logN)（以2为底）

空间复杂度：O(logN)

稳定性：稳定的排序