伊犁哈萨克自治州网站建设_网站建设公司_轮播图_seo优化

一，认识排序

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持 不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳 定的；否则称为不稳定的。

如： 排序前 2 536 12 32314

排序后 2335 6 12 14 32（稳定）

2335 6 12 14 32（不稳定）

内部排序：数据元素全部放在内存中的排序。

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

1.2 常见的排序算法

二，算法实现

2.1 插入排序

基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到 一个新的有序序列 。

2.1.1 直接插入排序

基本思想：当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i 1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

代码实现：

//直接插入排序 //有j和i两个下标，i往后走取元素，j往前-，用来比大小。tmp存放i下标所对应的值 public static void insetSort(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 { array[j + 1] = tmp; break;//j小于tmp，直接把tmp放在j后一个位置 } } array[j + 1] = tmp;//j到下标-1位置，把tmp值给j+1； } }

特性总结：

1.稳定性：稳定

2.时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4.元素集合越接近有序，直接插入排序算法的时间效率越高

2.1.2 希尔排序（缩小增量排序）

基本思想：先选定一个整数，把待排序文件中所有记录分成多个组， 所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达 =1时，所有记录在统一组内排好序。

代码实现：

//希尔排序 //取gap当gap=1时趋于有序，完成优化 public static void shellsort(int[] array) { int gap = array.length; while (gap > 1) { gap /= 2; shell(array, gap); } } private static void shell(int[] array, int gap) { for (int i = gap; i < array.length; i++) { //这里i++不是加gap是因为如果加gap会跳过很多元素只有加加跨组跳跃排序 int j = i - gap; int tmp = array[i]; for (; j >= 0; j -= gap) { if (array[j] > tmp) { array[j + gap] = array[j]; } else { array[j + gap] = tmp; break; } } array[j + gap] = tmp; } }

特性总结：

1.稳定性：不稳定

2.时间复杂度：O(N^1.3)到O（N^1.5）

(希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排 序的时间复杂度都不固定,所以取这个区间)

3. 空间复杂度：O(1)

4.希尔排序是对直接插入排序的优化. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很 快。这样整体而言，可以达到优化的效果

2.2 选择排序

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

2.2.1 直接选择排序

基本思想：

1.在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素

2.若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

3.在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

代码实现：（！！！swap方法为交换数组的两个元素，此方法多次调用，代码实现在文章末）

1，只选取最小值来排序

public static void selectSort1(int[] array) { for (int i = 0; i < array.length; i++) { int min = i; for (int j = 1 + i; j < array.length; j++) { if (array[j] < array[min]) { min = j; } } swap(array, i, min); } }

2，同时选最大最小值排序，和只取一个最值相比得到优化

//同时选最大值和最小值,i遍历找到最大最小下标记录，然后left和right缩小范围 public static void selectSort2(int[] array) { int left = 0; int right = array.length - 1; while (left < right) { int min = left; int max = left; for (int i = left + 1; i <= right; i++) { if (array[i] < array[min]) { min = i; } if (array[i] > array[max]) { max = i; } } swap(array, left, min); if (max == left) { //如果数组第一个元素为最大值，此时把left下标放入min，需要换回来 max = min; } swap(array, right, max); left++; right--; } }

特性总结：

1.稳定性：不稳定

2.时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4.直接选择排序思考效率不是很好。实际中很少使用

2.2.2 堆排序

基本思想：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆！！将最后下标元素与0下标交换后最后下标减1直到到1下标

代码实现：

//堆排序，创建大根堆，把0下标位置和最后一个下标换 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--; } } private static void createHeap(int[] array) { for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) { siftDown(array, parent, array.length); } } //parent每棵子树的开始结点 length没棵子树的结束结点 private static void siftDown(int[] array, int parent, int length) { int child = parent * 2 + 1; while (child < length) { if (child + 1 < length && array[child] < array[child + 1]) { child++; } if (array[child] > array[parent]) { swap(array, parent, child); parent = child; child = parent * 2 + 1; } else { break; } } }

特性总结：

1.稳定性：不稳定

2.时间复杂度：O(NlogN）

3. 空间复杂度：O(1)

4.堆排序使用堆来选数，效率高了很多

2.3 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1 冒泡排序

基本思想：对数组的相邻元素比较，如果从小到大排序时，前一个元素大于后一个元素则交换位置。继续比较下一对元素，直到队伍有序

代码实现：

//冒泡排序 加上flg进行优化 public static void bubbleSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { boolean flg = false; 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) {//当flg为false时说明没有交换直接出循环 break; } } }

特性总结：

1.稳定性：稳定

2.时间复杂度：O(N^2）

3. 空间复杂度：O(1)

2.3.2 快速排序

基本思想为：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

代码实现有Hoare版，挖坑法，前后指针法，下面一一介绍

总体代码实现：（这里优化基准值的选择）

public static void quickSort(int[] array) { quick(array, 0, array.length - 1); } private static void quick(int[] array, int start, int end) { if (start >= end) { return; } //优化 /*少的部分用直接插入排序 if(end-start+1<=10){ insertSortRange(array,start,end); return; } * */ /*三数取中 int mind=getMind(array,start,end); swap(array,start,mind);*/ int pivot = partition(array, start, end); partition(array, start, pivot - 1); partition(array, pivot, end); } //优化部分，直接插入 /*private static void insertSortRange(int[] array, int start, int end) { for (int i = start + 1; i <= end; i++) { int tmp = array[i]; int j = i - 1; for (; j >= start; j--) { if (array[j] > tmp) { array[j + 1] = array[j]; } else { array[j + 1] = tmp; break; } } array[j + 1] = tmp; } }*/ //优化部分，三数取中 /*private static int getMind(int[] array, int left, int right) { int mind = (left + right) / 2; if (array[left] < array[right]) { if (array[mind] < array[left]) { return left; } else if (array[mind] > array[right]) { return right; } else { return mind; } } else { if (array[mind] > array[left]) { return left; } else if (array[mind] < array[right]) { return right; } else { return mind; } }*/ }

挖坑法：取出基准值放入tmp，将此位置看为一个坑。从后往前走，遇到比基准小的值，直接进行覆盖，此位置变为新坑；从前往后走遇到比基准大的值，直接进行覆盖，此位置变为新坑

//挖坑法 private static int partition2(int[] array, int left, int right) { int tmp = array[left]; while (left < right) {//第一次判断整体数组是否满足合规 while (left < right && array[right] >= tmp) { //第二次判断right值是否合规 right--; } array[left] = array[right];//直接覆盖 while (left < right && array[left] <= tmp) { left++; } array[right] = array[left]; } array[left] = tmp; return left; }

Hoare法：从后找到比基准小的停下来，从前找到比基准大的停下来，相遇时把相遇树和基准换

//hoare法 private static int partition(int[] array, int left, int right) { int tmp = array[left]; int tmpleft = left; while (left < right) {//第一次判断整体数组是否满足合规 while (left < right && array[right] >= tmp) { //第二次判断right值是否合规 right--; } while (left < right && array[left] <= tmp) { left++; } swap(array, right, left); } swap(array, left, tmpleft); return left; }

前后指针法

private static int partition3(int[] array, int left, int right) { int prev = left; int cur = left + 1; while (cur <= right) { if (array[cur] < array[left] && array[++prev] != array[cur]) { swap(array, cur, left); } cur++; } swap(array, prev, left); return prev; }

快速排序的非递归实现：

//非递归方法 使用栈存放两个元素 public static void quickNor(int[] array, int start, int end) { Stack<Integer> st = new Stack<>(); int pivot = partition(array, start, end); if (pivot > start + 1) {//左边有至少两个元素 st.push(start); st.push(pivot - 1); } if (pivot < end - 1) { st.push(pivot + 1); st.push(end); } while (!st.isEmpty()) { end = st.pop(); start = st.pop(); pivot = partition(array, start, end); if (pivot > start + 1) {//左边有至少两个元素 st.push(start); st.push(pivot - 1); } if (pivot < end - 1) { st.push(pivot + 1); st.push(end); } } }

特性总结： （！！！最坏情况是给的值有序如：1，2，3，4，5，6或6，5，4，3，2，1）

1.稳定性：不稳定

2.时间复杂度：最好情况下 ：O(NlogN）最坏情况下：O（N^2）

3. 空间复杂度：最好情况下 ：O(logN)最坏情况下：O（N）

4.快速排序整体的综合性能和使用场景都是比较好的

2.4 归并排序

采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

代码实现：

//归并排序 public static void mergeSort(int[] array, int left, int right) { mergeSortTmp(array, 0, array.length - 1); } private static void mergeSortTmp(int[] array, int left, int right) { if (left >= right) { return; } int mid = (left + right) / 2; mergeSortTmp(array, left, mid); mergeSortTmp(array, mid + 1, right);//分解完毕 //开始合并 merge(array, left, mid, right); } private static void merge(int[] array, int left, int mid, int right) { int[] tmp = new int[right - left + 1]; int k = 0; int s1 = left; int e1 = mid; int s2 = mid + 1; int e2 = right; while (s1 <= mid && s2 <= right) { if (array[s1] <= array[s2]) { tmp[k++] = array[s1++]; } else { tmp[k++] = array[s2++]; } } while (s1 <= mid) { tmp[k++] = array[s1++]; } while (s2 <= right) { tmp[k++] = array[s2++]; } for (int i = 0; i < k; i++) { array[i + left] = tmp[i]; //i+left保证后一组需要合并的数，最开始的值不会被覆盖，是有序排列 } }

非递归实现：

/*非递归排序，定义gap，即每组有几个元素 public static void mergeSortNor(int[] array){ int gap=1; while(gap<array.length){ for(int i=0;i<array.length;i=i+gap*2){ int left=i; int mid=left+gap-1; if(mid>=array.length){ mid=array.length-1; //防止越界 } int right=mid+gap; if(right>=array.length){ right=array.length-1; //防止越界 } merge(array,left,mid,right); } } gap*=2; } * */

特性总结：

1.稳定性：稳定

2.时间复杂度：O(NlogN）

3. 空间复杂度：O（N）

2.5 对比总结

三，其他非基于比较的排序

3.1 计数排序

基本思想：

1.统计相同元素出现次数

2. 根据统计的结果将序列回收到原来的序列中

代码实现：

//计数排序 public static void countSort(int[] array){ //找最大最小值 int max=array[0]; int min=array[0]; for (int i = 0; i < array.length; i++) { if(array[i]<min){ min=array[i]; } if(array[i]>max){ max=array[i]; } } int len=max-min+1; int[] count=new int[len]; //遍历原来数组array，把每个元素 放到对应计数数组中，进行计数 for (int i = 1; i < array.length; i++) { int index=array[i]; count[index-min]++;//处理重复元素 } //依次遍历计数数组 int index=0; for(int i=0;i<count.length;i++){ while(count[i]!=0){ array[index]=i+min; index++; count[i]--; } } }

特性总结：

1.稳定性：稳定

2.时间复杂度：O(N+范围）

3. 空间复杂度：O（范围）

4.适用于集中在某个范围内的数据

3.2 基数排序

基本思想：按“位”排序，从数字的最低为到最高位依次对所有元素进行“分配-收集”

1.确定排序的“最高位数”

2.从最低位开始，用“桶”分配元素：将当前位数字相同的元素放入对应编号的桶中

3.按桶的顺序收集元素，组成新的有序数组

3.3 桶排序

基本思想：分而治之，先将待排序数据按范围“分配”到多个有序的“桶”中，再对每个桶内数据单独排序（可复用其他排序算法），最后按桶的顺序“收集”所有数据，得到整体有序结果。

1.确定桶的数量和每个桶的数值范围

2.遍历原始数组，将每个元素按数值范围放入对应的桶中

3.对每个非空桶内的元素进行排序

4.按桶的顺序（从小到大）依次取出所有桶内的排序后元素，拼接成最终的有序数组

四，总结

写这么久不做总结是不可能的，我的天啊天啊，最开始听的时候感觉很简单，等所有内容听完了，发现之前听的都糊在一起了，然后就开始敲敲敲把它们都拆分出来，太不容易（呜呜呜）。这是我第一篇写那么长的博客，太有成就感了！昨天晚上刷翁恺说的话，个人觉得还是很不错的鸡汤，分享给大家：“计算机的所有东西都是人做出来的，别人能想出来，我也一定能想出来，计算机里头没有任何黑魔法，所有的东西只不过是我现在不知道而已”！关关难过关关过，加油吧大家。如果方便的话还是动动发财的小手给我点点赞吧，谢谢大哥大姐弟弟妹妹们了。