网站学什么,wordpress1g内存,湖北专业网站建设质量保障,广州域名企业网站建站哪家好1 引言
常见的排序算法有八种#xff1a;交换排序【冒泡排序、快速排序】、插入排序【直接插入排序、希尔排序】、选择排序【简单选择排序、堆排序】、归并排序、基数排序。
2 交换排序
所谓交换#xff0c;就是序列中任意两个元素进行比较#xff0c;根据比较结果来交换…1 引言
常见的排序算法有八种交换排序【冒泡排序、快速排序】、插入排序【直接插入排序、希尔排序】、选择排序【简单选择排序、堆排序】、归并排序、基数排序。
2 交换排序
所谓交换就是序列中任意两个元素进行比较根据比较结果来交换各自在序列中的位置以此达到排序的目的。
2.1 冒泡排序
冒泡排序是一种简单的交换排序算法以升序排序为例其核心思想是
从第一个元素开始比较相邻的两个元素。如果第一个比第二个大则进行交换。轮到下一组相邻元素执行同样的比较操作再找下一组直到没有相邻元素可比较为止此时最后的元素应是最大的数。除了每次排序得到的最后一个元素对剩余元素重复以上步骤直到没有任何一对元素需要比较为止。 public void bubbleSortOpt(int[] nums) {if (nums null) {return;}int temp;for (int i 0; i nums.length; i) {for (int j 0; j nums.length - 1 - i; j) {if (nums[j] nums[j 1]) {temp nums[j];nums[j] nums[j 1];nums[j 1] temp;}}}}2.2 快速排序
快速排序的思想很简单就是先把待排序的数组拆成左右两个区间左边都比中间的基准数小右边都比基准数大。接着左右两边各自再做同样的操作完成后再拆分再继续一直到各区间只有一个数为止。
举个例子现在我要排序 4、9、5、1、2、6 这个数组。一般取首位的 4 为基准数第一次排序的结果是
2、1、4、5、9、6
可能有人觉得奇怪2 和 1 交换下位置也能满足条件为什么 2 在首位这其实由实际的代码实现来决定并不影响之后的操作。以 4 为分界点对 2、1、4 和 5、9、6 各自排序得到
1、2、4、5、9、6
不用管左边的 1、2、4 了将 5、9、6 拆成 5 和 9、6再排序至此结果为
1、2、4、5、6、9
为什么把快排划到交换排序的范畴呢因为元素的移动也是靠交换位置来实现的。算法的实现需要用到递归拆分区间之后再对每个区间作同样的操作 public void quicksort(int[] arr, int start, int end) {if (start end) {int stard arr[start];int low start;int high end;while (low high) {while (low high stard arr[high]) {high--;}arr[low] arr[high];while (low high stard arr[low]) {low;}arr[high] arr[low];}arr[low] stard;quicksort(arr, start, low);quicksort(arr, low 1, end);}}3 插入排序
插入排序是一种简单的排序方法其基本思想是将一个记录插入到已经排好序的有序表中使得被插入数的序列同样是有序的。按照此法对所有元素进行插入直到整个序列排为有序的过程。
3.1 直接插入排序
直接插入排序就是插入排序的粗暴实现。对于一个序列选定一个下标认为在这个下标之前的元素都是有序的。将下标所在的元素插入到其之前的序列中。接着再选取这个下标的后一个元素继续重复操作。直到最后一个元素完成插入为止。我们一般从序列的第二个元素开始操作。 public void insertSort(int[] nums) {// 遍历所有数字for (int i 1; i nums.length; i) {if (nums[i] nums[i - 1]) {// 把当前遍历的数字保存一下int temp nums[i];int j;// 前一个数字按序移动到后一个数字上for (j i - 1; j 0 nums[j] temp; j--) {nums[j 1] nums[j];}nums[j 1] temp;}}}3.2 希尔排序
某些情况下直接插入排序的效率极低。比如一个已经有序的升序数组这时再插入一个比最小值还要小的数也就意味着被插入的数要和数组所有元素比较一次。我们需要对直接插入排序进行改进。
怎么改进呢前面提过插入排序对已经排好序的数组操作时效率很高。因此我们可以试着先将数组变为一个相对有序的数组然后再做插入排序。
希尔排序能实现这个目的。希尔排序把序列按下标的一定增量步长分组对每组分别使用插入排序。随着增量步长减少一直到一算法结束整个序列变为有序。因此希尔排序又称缩小增量排序。
一般来说初次取序列的一半为增量以后每次减半直到增量为一。 public void shellSort(int[] nums) {for (int gap nums.length / 2; gap 0; gap / 2) {for (int i 0; i gap; i) {for (int j i gap; j nums.length; j gap) {if (nums[j] nums[j - gap]) {int k;int temp nums[j];for (k j - gap; k 0 nums[k] temp; k - gap) {nums[k gap] nums[k];}nums[k gap] temp;}}}}}4 选择排序
选择排序是一种简单直观的排序算法首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。
4.1 简单选择排序
选择排序思想的暴力实现每一趟从未排序的区间找到一个最小元素并放到第一位直到全部区间有序为止。 public void selectSort(int[] nums) {for (int i 0; i nums.length; i) {int minIndex i;for (int j i 1; j nums.length; j) {if (nums[j] nums[minIndex]) {minIndex j;}}if (i ! minIndex) {int temp nums[i];nums[i] nums[minIndex];nums[minIndex] temp;}}}4.2 堆排序
我们知道对于任何一个数组都可以看成一颗完全二叉树。堆是具有以下性质的完全二叉树每个结点的值都大于或等于其左右孩子结点的值称为大顶堆或者每个结点的值都小于或等于其左右孩子结点的值称为小顶堆。如下图 像上图的大顶堆映射为数组就是 [50, 45, 40, 20, 25, 35, 30, 10, 15]。可以发现第一个下标的元素就是最大值将其与末尾元素交换则末尾元素就是最大值。所以堆排序的思想可以归纳为以下两步
根据初始数组构造堆
每次交换第一个和最后一个元素然后将除最后一个元素以外的其他元素重新调整为大顶堆
重复以上两个步骤直到没有元素可操作就完成排序了。
我们需要把一个普通数组转换为大顶堆调整的起始点是最后一个非叶子结点然后从左至右从下至上继续调整其他非叶子结点直到根结点为止。
/*** 转化为大顶堆* 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);}
}/*** 堆排序* param arr 待排序的整型数组*/
public static void heapSort(int[] arr) {// 开始位置是最后一个非叶子结点即最后一个结点的父结点int start (arr.length - 1) / 2;// 调整为大顶堆for (int i start; i 0; i--) {SortTools.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);}
}5 归并排序
归并排序是建立在归并操作上的一种有效稳定的排序算法。该算法采用分治法的思想是一个非常典型的应用。归并排序的思路如下
将 n 个元素分成两个各含 n/2 个元素的子序列借助递归两个子序列分别继续进行第一步操作直到不可再分为止此时每一层递归都有两个子序列再将其合并作为一个有序的子序列返回上一层再继续合并全部完成之后得到的就是一个有序的序列
关键在于两个子序列应该如何合并。假设两个子序列各自都是有序的那么合并步骤就是
创建一个用于存放结果的临时数组其长度是两个子序列合并后的长度设定两个指针最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素选择相对小的元素放入临时数组并移动指针到下一位置重复步骤 3 直到某一指针达到序列尾将另一序列剩下的所有元素直接复制到合并序列尾
/*** 合并数组*/
public static 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 static 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);}
}6 基数排序
基数排序的原理是将整数按位数切割成不同的数字然后按每个位数分别比较。为此需要将所有待比较的数值统一为同样的数位长度数位不足的数在高位补零。
/*** 基数排序*/
public static void radixSort(int[] arr) {// 存放数组中的最大数字int max Integer.MIN_VALUE;for (int value : arr) {if (value max) {max value;}}// 计算最大数字是几位数int maxLength (max ).length();// 用于临时存储数据int[][] temp new int[10][arr.length];// 用于记录在 temp 中相应的下标存放数字的数量int[] counts new int[10];// 根据最大长度的数决定比较次数for (int i 0, n 1; i maxLength; i, n * 10) {// 每一个数字分别计算余数for (int j 0; j arr.length; j) {// 计算余数int remainder arr[j] / n % 10;// 把当前遍历的数据放到指定的数组中temp[remainder][counts[remainder]] arr[j];// 记录数量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;}}}
}7 算法性能
序号排序算法时间复杂度平均时间复杂度最坏时间复杂度最好空间复杂度稳定性1冒泡排序O(n^2)O(n^2)O(n)O(1)稳定2快速排序O(n log n)O(n^2)O(n log n)O(n log n)不稳定3直接插入排序O(n^2)O(n^2)O(n)O(1)稳定4希尔排序O(n log n)O(n^2)O(n)O(1)不稳定5简单选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定6堆排序O(n log n)O(n log n)O(n log n)O(n log n)不稳定7归并排序O(n log n)O(n log n)O(n log n)O(n)稳定8基数排序O(n*k)O(n*k)O(n*k)O(nk)稳定
返回面试宝典
