各大网站平台发布信息,临淄信息港最新招聘,wordpress中文版,百度收录自适应网站排序算法
交换排序 冒泡排序快速排序 插入排序 直接插入排序希尔排序 选择排序 简单选择排序堆排序 归并排序基数排序桶排序
一、冒泡排序
冒泡排序是一种简单的交换排序算法#xff0c;以升序排序为例#xff0c;其核心思想是#xff1a;
从第一个元素开始#xff0c…排序算法
交换排序 冒泡排序快速排序 插入排序 直接插入排序希尔排序 选择排序 简单选择排序堆排序 归并排序基数排序桶排序
一、冒泡排序
冒泡排序是一种简单的交换排序算法以升序排序为例其核心思想是
从第一个元素开始比较相邻的两个元素。如果第一个比第二个大则进行交换。轮到下一组相邻元素执行同样的比较操作再找下一组直到没有相邻元素可比较为止此时最后的元素应是最大的数。除了每次排序得到的最后一个元素对剩余元素重复以上步骤直到没有任何一对元素需要比较为止。
/*** 冒泡排序** param arr*/
public void bubbleSort(int[] arr) {int tmp;// 冒泡优化如果在某一次冒泡过程中没有发生交换则证明数组已经是有序的了for (int i 0; i arr.length; i) {boolean flag true;for (int j i 1; j arr.length; j) {if (arr[j] arr[i]) {flag false;tmp arr[j];arr[j] arr[i];arr[i] tmp;}}if (flag) {break;}}
}二、快速排序
快速排序的思想很简单就是先把待排序的数组拆成左右两个区间左边都比中间的基准数小右边都比基准数大。接着左右两边各自再做同样的操作完成后再拆分再继续一直到各区间只有一个数为止。
/*** 快速排序** param arr*/
public void quickSort(int[] arr, int low, int high) {if (low high) {return;}int left low;int right high;int baseIndex left;int base arr[baseIndex];int tmp;while (left right) {while (arr[right] base left right) {// 以base为基准从右往左找到比基准小的数right--;}while (arr[left] base left right) {// 以base为基准从左往右找到比基准大的数left;}if (left right) {// 左右还没相交大小对换位置tmp arr[left];arr[left] arr[right];arr[right] tmp;}}// 这一轮快排结束交换相遇点与基准点把基准数放在对应的位置上// 因为要把基准数和相遇点交换由于if判断包含等于那么从左往右就会找到比基准数小的数从右往左就会找到比基准数大的数会越过基准数// 因此当基准点小于相遇点时基准点取第一位数必须保证从先移动右指针再移动左指针当基准点大于相遇点时基准点取最后一位位数必须保证从先移动左指针再移动右指针// 如果一定要随机基准数有个简单的改进方法就是随机一位数与首位或最后一位先做一下交换tmp arr[baseIndex];arr[baseIndex] arr[right];arr[right] tmp;//数组“分两半”,再重复上面的操作quickSort(arr, low, left - 1);quickSort(arr, left 1, high);
}三、插入排序
插入排序是一种简单的排序方法其基本思想是将一个记录插入到已经排好序的有序表中使得被插入数的序列同样是有序的。按照此法对所有元素进行插入直到整个序列排为有序的过程。
1. 直接插入排序
直接插入排序就是插入排序的粗暴实现。对于一个序列选定一个下标认为在这个下标之前的元素都是有序的。将下标所在的元素插入到其之前的序列中。接着再选取这个下标的后一个元素继续重复操作。直到最后一个元素完成插入为止。我们一般从序列的第二个元素开始操作。
/*** 插入排序** param arr*/
public void insertSort(int[] arr) {// 从第二个数开始遍历for (int i 1; i arr.length; i) {// 插入的数int insertNum arr[i];// 寻找插入点int insertIndex 0;for (int j 0; j i; j, insertIndex) {// 插入点在比插入数大的这一位的前面if (insertNum arr[j]) {break;}}// 从插入点往后依次挪动for (int j i; j insertIndex; j--) {if (j 0) {arr[j] arr[j - 1];}}// 最后插入数据arr[insertIndex] insertNum;}
}插入排序对已经排好序的数组操作时效率很高
2. 希尔排序
某些情况下直接插入排序的效率极低。比如一个已经有序的升序数组这时再插入一个比最小值还要小的数也就意味着被插入的数要和数组所有元素比较一次。我们需要对直接插入排序进行改进。
我们可以试着先将数组变为一个相对有序的数组然后再做插入排序。
希尔排序的步骤简述如下 把元素按步长gap分组gap的数值其实就是分组的个数。gap的起始值为数列长度的一半每循环一轮gap减为原来的一半。对每组元素采用直接插入排序算法进行排序。随着步长逐渐减小组就越少组中包含的元素就越多。当步长值减小到1时整个数据合成一组最后再对这一组数列用直接插入排序进行最后的调整最终完成排序。 我们以无序数列[58639217,4]为例详细介绍希尔排序的步骤
(1). 第一轮排序gap length/2 4即将数组分成4组。四组元素分别为[594]、[82]、[61]、[3,7]。对四组元素分别进行排序结果为[459]、[28]、[16]、[37]。将四组排序结果进行合并得到第一轮的排序结果为[421358679]。如下图所示。 (2). 第二轮排序gap 2将数列分成2组。两组的元素分别是[41569]和[238,7]。这两个组分别执行直接插入排序后的结果为[14569]和[2378]。将两组合并后的结果为[124357689]如下图所示。 (3). 第三轮排序gap 1数组就变成了一组。该组的元素是[124357689]这个组执行直接插入排序后结果为[123456789]这个结果就是第三轮排序后得到的结果。此时排序完成如下图所示。
public void shellSort(int[] arr) {// gap 为步长每次减为原来的一半。for (int gap arr.length / 2; gap 0; gap / 2) {// 对每一组都执行直接插入排序for (int i 0 ;i gap; i) {// 对本组数据执行直接插入排序for (int j i gap; j arr.length; j gap) {// 如果 a[j] a[j-gap]则寻找 a[j] 位置并将后面数据的位置都后移if (arr[j] arr[j - gap]) {int k;int temp arr[j];for (k j - gap; k 0 arr[k] temp; k - gap) {arr[k gap] arr[k];}arr[k gap] temp;}}}}
}四、选择排序
1. 简单选择排序
选择排序思想的暴力实现每一趟从未排序的区间找到一个最小元素并放到第一位直到全部区间有序为止。
public void selectSort(int[] arr) {for (int i 0; i arr.length; i) {// 遍历数据int minIndex i;for (int j i 1; j arr.length; j) {// 从当前位置往后遍历找到最小数的下标if (arr[j] arr[minIndex]) {minIndex j;}}// 最小数的下标不是第一个数那么就把最小下标和第一个数做交换if (i ! minIndex) {int temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}}
}2. 堆排序
对于任何一个数组都可以看成一颗完全二叉树。堆是具有以下性质的完全二叉树
大顶堆每个结点的值都大于或等于其左右孩子结点的值小顶堆每个结点的值都小于或等于其左右孩子结点的值
像上图的大顶堆映射为数组就是 [50, 45, 40, 20, 25, 35, 30, 10, 15]。可以发现第一个下标的元素就是最大值将其与末尾元素交换则末尾元素就是最大值。所以堆排序的思想可以归纳为以下两步
将待排序的数组初始化为大顶堆该过程即建堆。将堆顶元素与最后一个元素进行交换除去最后一个元素外可以组建为一个新的大顶堆。由于第二部堆顶元素跟最后一个元素交换后新建立的堆不是大顶堆需要重新建立大顶堆。重复上面的处理流程直到堆中仅剩下一个元素。
重复以上两个步骤直到没有元素可操作就完成排序了。
我们需要把一个普通数组转换为大顶堆调整的起始点是最后一个非叶子结点然后从左至右从下至上继续调整其他非叶子结点直到根结点为止。
/*** 堆排序** param arr*/
public void heapSort(int[] arr) {// 开始位置是最后一个非叶子结点即最后一个结点的父结点int start (arr.length - 1) / 2;// 调整为大顶堆for (int i start; i 0; i--) {maxHeap(arr, arr.length, i);}// 先把数组中第 0 个位置的数和堆中最后一个数交换位置再把前面的处理为大顶堆for (int i arr.length - 1; i 0; i--) {int temp arr[0];arr[0] arr[i];arr[i] temp;maxHeap(arr, i, 0);}
}
/*** 转化为大顶堆** param arr 待转化的数组* param size 待调整的区间长度* param index 结点下标*/
public void maxHeap(int[] arr, int size, int index) {// 左子结点int leftNode 2 * index 1;// 右子结点int rightNode 2 * index 2;int max index;// 和两个子结点分别对比找出最大的结点if (leftNode size arr[leftNode] arr[max]) {max leftNode;}if (rightNode size arr[rightNode] arr[max]) {max rightNode;}// 交换位置if (max ! index) {int temp arr[index];arr[index] arr[max];arr[max] temp;// 因为交换位置后有可能使子树不满足大顶堆条件所以要对子树进行调整maxHeap(arr, size, max);}
}五、归并排序
归并排序是建立在归并操作上的一种有效稳定的排序算法。该算法采用分治法的思想是一个非常典型的应用。归并排序的思路如下
将 n 个元素分成两个各含 n/2 个元素的子序列借助递归两个子序列分别继续进行第一步操作直到不可再分为止此时每一层递归都有两个子序列再将其合并作为一个有序的子序列返回上一层再继续合并全部完成之后得到的就是一个有序的序列
关键在于两个子序列应该如何合并。假设两个子序列各自都是有序的那么合并步骤就是
创建一个用于存放结果的临时数组其长度是两个子序列合并后的长度设定两个指针最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素选择相对小的元素放入临时数组并移动指针到下一位置重复步骤 3 直到某一指针达到序列尾将另一序列剩下的所有元素直接复制到合并序列尾
/*** 合并数组*/
public void merge(int[] arr, int low, int middle, int high) {// 用于存储归并后的临时数组int[] temp new int[high - low 1];// 记录第一个数组中需要遍历的下标int i low;// 记录第二个数组中需要遍历的下标int j middle 1;// 记录在临时数组中存放的下标int index 0;// 遍历两个数组取出小的数字放入临时数组中while (i middle j high) {// 第一个数组的数据更小if (arr[i] arr[j]) {// 把更小的数据放入临时数组中temp[index] arr[i];// 下标向后移动一位i;} else {temp[index] arr[j];j;}index;}// 处理剩余未比较的数据while (i middle) {temp[index] arr[i];i;index;}while (j high) {temp[index] arr[j];j;index;}// 把临时数组中的数据重新放入原数组for (int k 0; k temp.length; k) {arr[k low] temp[k];}
}
/*** 归并排序*/
public void mergeSort(int[] arr, int low, int high) {int middle (high low) / 2;if (low high) {// 处理左边数组mergeSort(arr, low, middle);// 处理右边数组mergeSort(arr, middle 1, high);// 归并merge(arr, low, middle, high);}
}六、基数排序
基数排序的原理是将整数按位数切割成不同的数字然后按每个位数分别比较。为此需要将所有待比较的数值统一为同样的数位长度数位不足的数在高位补零。
/*** 基数排序** param arr*/
public void radixSort(int[] arr) {// 存放数组中的最大数字int max Integer.MIN_VALUE;for (int value : arr) {if (value max) {max value;}}// 计算最大数字是几位数int maxLength (max ).length();// 用于临时存储数据0-9int[][] temp new int[10][arr.length];// 用于记录在 temp 中相应的下标存放数字的数量0-9int[] counts new int[10];// 根据最大长度的数决定比较次数从低位往高位以此比较for (int i 0, n 1; i maxLength; i, n * 10) {// 每一个数字分别计算余数for (int value : arr) {// 计算余数int remainder value / n % 10;// 把当前遍历的数据放到指定的数组中temp[remainder][counts[remainder]] value;// 记录数量counts[remainder];}// 记录取的元素需要放的位置int index 0;// 把数字取出来for (int k 0; k counts.length; k) {// 记录数量的数组中当前余数记录的数量不为 0if (counts[k] ! 0) {// 循环取出元素for (int l 0; l counts[k]; l) {arr[index] temp[k][l];// 记录下一个位置index;}// 把数量置空counts[k] 0;}}}
}七、桶排序
桶排序Bucket Sort又称箱排序是一种比较常用的排序算法。其算法原理是将数组分到有限数量的桶里再对每个桶分别排好序可以是递归使用桶排序也可以是使用其他排序算法将每个桶分别排好序最后一次将每个桶中排好序的数输出。
桶排序的思想就是把待排序的数尽量均匀地放到各个桶中再对各个桶进行局部的排序最后再按序将各个桶中的数输出即可得到排好序的数。
首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn根据mx和mn确定每个桶所装的数据的范围 size有size (mx - mn) / n 1n为数据的个数需要保证至少有一个桶故而需要加个1
求得了size即知道了每个桶所装数据的范围还需要计算出所需的桶的个数cnt有cnt (mx - mn) / size 1需要保证每个桶至少要能装1个数故而需要加个1
求得了size和cnt后即可知第一个桶装的数据范围为 [mn, mn size)第二个桶为 [mn size, mn 2 * size)…以此类推因此步骤2中需要再扫描一遍数组将待排序的各个数放进对应的桶中。对各个桶中的数据进行排序可以使用其他的排序算法排序例如快速排序也可以递归使用桶排序进行排序将各个桶中排好序的数据依次输出最后得到的数据即为最终有序。
/*** 桶排序** param arr*/
public void bucketSort(int[] arr) {int n arr.length;int mn arr[0], mx arr[0];// 找出数组中的最大最小值for (int i 1; i n; i) {mn Math.min(mn, arr[i]);mx Math.max(mx, arr[i]);}// 每个桶存储数的范围大小使得数尽量均匀地分布在各个桶中保证最少存储一个int size (mx - mn) / n 1;// 桶的个数保证桶的个数至少为1int cnt (mx - mn) / size 1;// 声明cnt个桶ListInteger[] buckets new List[cnt];for (int i 0; i cnt; i) {buckets[i] new ArrayList();}// 扫描一遍数组将数放进桶里for (int k : arr) {int idx (k - mn) / size;buckets[idx].add(k);}// 对各个桶中的数进行排序这里用库函数快速排序for (int i 0; i cnt; i) {// 默认是按从小打到排序// 这里可以用任何的方式排序这里直接用List的sort方法buckets[i].sort(null);}// 依次将各个桶中的数据放入返回数组中int index 0;for (int i 0; i cnt; i) {for (int j 0; j buckets[i].size(); j) {arr[index] buckets[i].get(j);}}
}排序算法对比
排序算法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性冒泡排序O(n2)O(n2)O(n)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(n)O(1)稳定快速排序O(nlogn)O(n²)O(nlogn)O(nlogn)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定希尔排序O(n^1.3)O(n²)O(n)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定基数排序O(d(nk))O(d(nk))O(d(nk))O(nk)稳定桶排序O(nk)O(n²)O(n)O(nk)稳定 参考资料https://mp.weixin.qq.com/s?__bizMzAxMjY5NDU2Ngmid2651862169idx1sne011e79ff77736dfb389084bb3a20d37chksm804971d0b73ef8c649d7c9b08706f3c33b0e10c3935e24982337b05d69f1487ace072fbd48d9scene27
