赞
踩
稳定性:例如[a,b],a和b是相等的,当排完序后a和b的位置互换了就说明不稳定,没有互换就说明稳定。
算法都有优劣,了解算法的性能才能在实践中选择更好的算法,所以了解算法性能十分的必要。
在性能上对比归并排序、快速排序、堆排序是相对来说比较好的排序算法,可以重点理解下这些算法;希尔排序相对于以上三个并不是最好,但也可以重点学习理解,面试过程中考察点突发奇想,冒泡选择插入也说不定会考察。
在JDK中Array.sort()排序方法中,在数组长度小于286时,使用的是快速排序,而在数组长度小于47时使用的是插入排序。在JDK8中还有一点就是,在数组长度小于286大于47,并且数组具有一定结构,则使用归并排序。
算法描述:
1、将第一位当成最小值,记录值和下标,用最小值向右进行逐个比较,查找是否有更小的,有则更新最小的值和下标。
2、判断最小值下标是否变动,变动则交换位置,将新的最小值位置赋值为旧的最小值,旧的赋值为新的最小值。
静态图解
动图图解
代码部分
/** * 选择排序: * 外层循环的作用: * 选择排序执行的次数 * 内层循环的作用: * 将第一位当成最小值,记录值和下标,用最小值向右进行逐个比较,查找是否有更小的,有则更新最小的值和下标。 * 判断语句的作用: * 判断最小值下标是否变动,变动则交换位置,将新的最小值位置赋值为旧的最小值,旧的赋值为新的最小值。 */ @Test public void Test() { int[] arr = new int[]{-12, -55, -23, 43, 24, 34, 12}; SelectSortFun(arr); Arrays.stream(arr).forEach(i -> System.out.print(i + " ")); } public void SelectSortFun(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { // 选择排序执行的次数 int min = arr[i]; int minIndex = i; for (int j = i; j < arr.length; j++) { // 每次遍历确定最左边的一位最小值,所以从i开始。 if (min > arr[j+1]) { min = arr[j+1]; minIndex = j+1; } } if (i != minIndex) { // 最小值有变动,不是原来的那个,则交换。 arr[minIndex] = arr[i]; // 查找到的最小值下标赋值为下标i的数 arr[i] = min; // 下标i赋值为最小值 } } }
算法描述:两两进行比较,从左开始,5大于2则交换,5大于1则交换,如果有比5大的,则将自身下标设置为更大的值的下标,继续向后比较,直到自身为最大,则确定了数组最右边为第一个最大值,同理逐个确定,直到只剩一个则完成排序。
静态图解
动图图解
代码部分
@Test public void Test() { int[] arr = new int[]{-12, -55, -23, 43, 24, 34, 12}; BubbleSortFun(arr); Arrays.stream(arr).forEach(i -> System.out.print(i + " ")); } public void BubbleSortFun(int[] arr) { boolean flag = true; //优化有序数组多次进行循环,当遇到没交换位置的情况则提前终止循环 for (int i = 0; i < arr.length - 1; i++) { // 冒泡的次数 for (int j = 0; j < arr.length - i - 1; j++) { // 每次冒泡确定了最后一位数字,所以减i,防止再次遍历后面的数浪费时间。 if (arr[j] > arr[j + 1]) { flag = false; // 进去了说明有无序数组则不跳过继续循环,没进去才跳过停止循环 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } if (flag) { break; } } }
算法描述:认为第一个元素已经排序,从第二个元素开始(也就是下标1开始),取出下一个元素,向左扫描,如果取出的元素小于向左扫描的元素,则将扫描到的元素向右移,将取出的元素移动到比他更小的值的前一位。
动图图解
代码部分
@Test public void Test() { int[] arr = new int[]{-12, -55, -23, 43, 24, 34, 12}; insertionSort(arr); Arrays.stream(arr).forEach(i -> System.out.print(i + " ")); } public int[] insertionSort(int[] arr) { int preIndex,current; // pre是下一个需要排序的元素,cur是当前元素的备份值 for (int i = 1; i < arr.length; i++) { preIndex = i - 1; // 移动的下标 current = arr[i]; // 记录被覆盖的值 while (preIndex >= 0 && arr[preIndex] > current) { // arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex + 1] = current; // 如果移动:将移动后的位置插入被覆盖的值 } return arr; }
算法描述:
1、确定初始增量大小(增量大小必须大于等于1)
2、分组进行插入排序
3、从最小增量2,开始插入排序,排完后再排序增量4,直到整个数组排序。
静态图解
代码部分
 /** * 希尔排序原理: * 将数组按照增量gap进行分组,然后将每组内的数字进行插入排序, * 排序完后增量减小,继续排序,直至减少到1后再进行最后一次插入排序。 */ @Test public void Test(){ int[] arr = new int[]{-12, -55, -23, 43, 24, 34, 12}; sort(arr); Arrays.stream(arr).forEach(i -> System.out.print(i + " ")); } public int[] sort(int[] arr) { int current; /* 按照增量分组,每一组内进行插入排序 */ /* gap是指用来分组的增量,必须是依次递减的 */ int gap = arr.length/2; while (gap > 0) { /* 从gap开始可以节约一点运算时间,少循环几次 */ for (int i = gap; i < arr.length; i++) { int preIndex = i - gap; current = arr[i]; while (preIndex >= 0 && arr[preIndex] > current) { arr[preIndex + gap] = arr[preIndex]; preIndex -= gap; } arr[preIndex + gap] = current; } gap /= 2; } return arr; }
算法描述:
1、确定基准数
2、将基准数与最右或者最左交换位置(若基准数本身就在最左最右则不必交换)
3、一刀切,使用基准数(可以分区大小范围内随机,也可直接设置最左或最右)确定中间值,左边为比基准数更小的,右边是比基准数更大的
4、细化分区,循环第三步的做法。
分区操作
1、如果元素小于等于基准数,则分区指示器右移
2、在1的基础上,如果当前元素下标(遍历指示器)大于分区指示器下标时,则当前元素和分区指示器元素交换。
注意:基准数只是一个不会变动的下标,当交换时基准数下标是不会变动的,但是基准数下标的值会不断变动
动态图解(通俗易懂的)
正经点的
代码部分
 /** * 快速排序 */ @Test public void Test(){ int[] arr = new int[]{-12, -55, -23, 43, 24, 34, 12}; arr = sort(arr, 0, arr.length - 1); Arrays.stream(arr).forEach(i -> System.out.print(i + " ")); } // 排序操作 public int[] sort(int[] arr, int left, int right) { if (arr.length < 1 || left < 0 || right >= arr.length || left > right) return null; int index = partition(arr, left, right); // if (index > left) { // index为比基准数大的下标位 sort(arr, left, index - 1); } else if(index < right) { sort(arr, index + 1, right); } return arr; } /** * 分区操作:一分为二,左边的是比基准数小的,右边的是比基准数大的。 * @param arr * @param left * @param right * @return */ public int partition(int[] arr, int left, int right) { if (left == right) return left; // 设置基准数:如果基准数设置最左或者最左时则此处可以用right或者left代替 int pivot = new Random().nextInt(arr.length); // 设置分区指示器:初始值必须是遍历指示器-1 int index = left - 1; for (int i = left; i <= right; i++) { // i是遍历指示器 if (arr[i] <= arr[pivot]) { // 遍历值小于等于基准数,则分区指示器+1(向右移一位) index++; if (i > index) { // 遍历指示器大于分区指示器的时候,则交换位置 swap(arr,i, index); } } } return index; } public void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
算法描述:采用的是分而治之的方法,将数组逐个拆分,拆到只剩一个或者两个(拆成多少个都可以排序,但是不能低于0个)再进行比较后从小到大合并合并。
合并过程:现将左右两边数组第一位进行比较,如果右边的小,则临时数组插入右边数组值,右边下标指示器+1,若左边数组值小于右边数组值,则临时数组插入左边下标值,左边下标指示器+1,若下标指示器等于数组长度时,说明一遍数组已经排序完毕,则直接一次插入右边数组的值即可。
静态图解
动态图解
代码部分
 /** * 归并排序: * 采用的是分而治之的方法,将数组逐个拆分,拆到只剩一个或者两个(拆成多少个都可以排序,但是不能低于0个)再进行比较后从小到大合并合并。 */ @Test public void Test() { int[] arr = new int[]{-12, -55, -23, 43, 24, 34, 12, -55, 5, 6, 43, 65}; arr = margeSort(arr); Arrays.stream(arr).forEach(i -> System.out.print(i + " ")); } public int[] margeSort(int[] arr) { if (arr.length < 2) return arr; int mid = arr.length / 2; int[] left = Arrays.copyOfRange(arr, 0, mid); int[] right = Arrays.copyOfRange(arr, mid, arr.length); return marge(margeSort(left), margeSort(right)); } public int[] marge(int[] left, int[] right) { int[] result = new int[left.length + right.length]; for (int index = 0, i = 0, j = 0; index < result.length; index++) { if (i >= left.length) // 左边数组已经取完,直接拿右边数组的值即可 result[index] = right[j++]; else if (j >= right.length) // 右边数组已经取完,直接拿左边数组的值即可 result[index] = left[i++]; else if (left[i] > right[j]) // 左边数组元素值大于右边数组,取右边数组 result[index] = right[j++]; else // 右边数组元素值大于左边数组,取左边数组 result[index] = left[i++]; } return result; } 
算法描述:
1、将原始数组构造为最大堆。
2、不停的将头元素和尾元素进行交换,交换后尾元素则为最大值,将他存入结果数组中。
3、交换后再次构造最大堆,重复步骤2和3,最终排序完成。
扩展-二叉堆的定义:二叉堆是一个完全二叉树的结构,同时满足堆的性质,子节点的键值或者索引总是小于(或大于)它的父节点。在一个二叉堆中,根节点总是最大(或者最小)节点,这样的堆称之为最大(小)堆
扩展-完全平方二叉树:
推论1:对于位置为K的节点,左子节点=2xK+1,右子节点=2x(K+1) 验证:C=2 2x2+1=5 2x(2+1)=6
推论2:最后一个非叶子节点的位置为(N/2)-1,N为数组长度 验证:数字长度为6,(6/2)-1=2
动态图解
代码部分
/** * 定义长度为全局变量,用于记录堆排序的剩余数组长度 */ public static int len; /** * 堆排序 */ @Test public void Test() { int[] arr = new int[]{-12, -55, -23, 43, 24, 34, 12, -55, 5, 6, 43, 65}; sortArray(arr); MyArrayUtil.printArray(arr); } public int[] sortArray(int[] arr) { len = arr.length; if (len < 1) { return arr; } /* 1.构建最大堆 */ buildMaxHeap(arr); /* 2.循环将堆首位(最大值)与未排序数据末位交换,然后调整为最大值*/ while (len > 0) { /* 交换首尾,将末尾元素放置最大值 */ MyArrayUtil.swap(arr, 0, len - 1); len--; buildMaxHeap(arr); MyArrayUtil.printArray(arr); } return arr; } /** * 构建最大堆 * @param arr */ public static void buildMaxHeap(int[] arr) { for (int i = (len/2 -1); i >= 0; i--) { /* i为最小非叶子结点在数组中的下标 */ adjustHeap(arr,i); } } /** * 调整最大堆 * @param arr * @param i */ public static void adjustHeap(int[] arr, int i) { int maxIndex=i; int left = 2*i-1; int right = 2*(i+1); if (left < len && arr[left] > arr[maxIndex]) { maxIndex = left; } if (right < len && arr[right] > arr[maxIndex] && arr[right] > arr[left]) { maxIndex = right; } if (maxIndex != i) { /* 将最大值和父节点进行交换,使父节点成为最大值 */ MyArrayUtil.swap(arr,maxIndex,i); adjustHeap(arr,maxIndex); } }
算法描述:
1、构建最大值长度的数组。
2、遍历数组,将遍历的数字作为构建数组的下标,遍历一次则+1计数。
3、从数组最小值到数组最大值遍历构建数组(节约遍历空间),当数组下标对应的值不为0,则结果数组的值设置为下标值。
实际应用:实际应用会找出数组中的最大值和最小值,主要为了节省空间,例如【1001,1002,1005,1002】这样的数组没必要建立1005个长度的数组。
适用范围:适用于排序元素分布连续,且跨度小的情况。
存在的问题:无法解决小数情况,且负数情况需要进一步处理
动态图解
代码部分
/** * 计数排序 */ @Test public void Test() { int[] arr = new int[]{12, 55, 23, 43, 24, 34, 12}; sortArray(arr); MyArrayUtil.printArray(arr); } public int[] sortArray(int[] arr) { int maxVal = arr[0]; int minVal = arr[0]; // 查找最大值和最小值,构建临时数组的长度(节约空间) for (int i = 1; i < arr.length; i++) { if (maxVal < arr[i]) { maxVal = arr[i]; } if (minVal > arr[i]) { minVal = arr[i]; } } int[] temp = new int[maxVal-minVal+1]; // 遍历数组中每个值,用于临时数组的下标 for (int k : arr) { // 在指定下标+1,计数 temp[k - minVal]++; } // 第一种写法 /*for (int i = 0,j=0; i < temp.length; i++) { while (temp[i] != 0) { arr[j] = i + minVal; j++; temp[i]--; } }*/ // 第二种写法 /* 访问原数组的下标指示器 */ int index = 0; /* 访问计数数组的下标指示器 */ int i = 0; while (index < arr.length) { if (temp[i] != 0) { arr[index] = i + minVal; index++; temp[i]--; } else { i++; } } return arr; }
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。
算法描述:
1、创建一定量的数组当做桶。
2、遍历数组将每个数据放入规定范围(可能是[0,10],[10,20],[20,30)这个样子的)的桶中
3、对每个桶进行排序
存在的问题:1、排序的数组可能趋近一个范围内,导致所有数组中所有数都放入一个桶中,失去了桶排序的意义。 2、事先不知道输入的数据是什么,为了保证每个元素均匀分布到各个桶中,需要建立多少个桶,每个桶的范围是多少并不知道。
实际应用:简单点的有,限定桶的容量,根据元素最大值和最小值相减来决定桶的数量。
动态图解
代码部分
/** * 桶排序 */ @Test public void test() { ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(-12); arr.add(-55); arr.add(23); arr.add(34); arr.add(31); arr.add(83); arr.add(34); arr.add(65); arr.add(23); arr = bucketSort(arr, 2); System.out.println(arr); } public ArrayList<Integer> bucketSort(ArrayList<Integer> array, int bucketCap) { if (array == null || array.size() < 2) { return array; } int max = array.get(0), min = array.get(0); /* 找到最大值和最小值 */ for (Integer num : array) { if (max < num) { max = num; } if (min > num) { min = num; } } /* 获得桶的数量 */ int bucketCount = (max - min) / bucketCap + 1; /* 构建桶 */ ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount); ArrayList<Integer> resultArr = new ArrayList<>(); for (int i = 0; i < bucketCount; i++) { bucketArr.add(new ArrayList<>()); } /* 将原始数据分配到桶中(分配的过程中就可以排好了一部分顺序): 分配规则为, 下标值=(遍历的值-最小值)/ 桶容量 数据=遍历值 */ for (int i = 0; i < array.size(); i++) { bucketArr.get((array.get(i) - min) / bucketCap).add(array.get(i)); } /* 查看桶中的分布情况 */ for (int i = 0; i < bucketArr.size(); i++) { System.out.print("第" + i + "个桶包含数据:"); System.out.println(bucketArr.get(i)); } /* 遍历所有桶 */ for (int i = 0; i < bucketCount; i++) { if (bucketCap == 1 ){ resultArr.addAll(bucketArr.get(i)); } else { if (bucketCount == 1) { bucketCap--; } /* 对桶中数据再次进行桶排序 */ List<Integer> temp = bucketSort(bucketArr.get(i), bucketCap); /* 将所有排序好的桶进行合并 */ resultArr.addAll(temp); } } return resultArr; }
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。
算法描述:
1、遍历数组,获取最大值,并获取最大值的位数,确定遍历轮数。
2、遍历数组,根据个位(十位、百位等)按照下标入桶。
3、取出桶中所有数字,循环执行步骤2和步骤3
存在的问题:该代码不可用于有小数类型的数组,负数需要进一步处理。
动态图解
代码部分
/** * 基数排序 */ @Test public void Test() { int[] arr = new int[]{32, 5, 52, 34, 43, 24, 34, 12}; sortArray(arr); Arrays.stream(arr).forEach(i -> System.out.print(i + " ")); } public int[] sortArray(int[] arr) { /* 找出最大值的位数,确定需要做几轮排序 */ int max = 0; for (int num : arr) { max = Math.max(max, num); } /* 确定位数 */ int maxDigit = 0; while (max != 0) { max /= 10; maxDigit++; } /* 用于获得数字指定位数 */ int mod = 10, div = 1; /* 构建桶 */ ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(); /* 初始化桶 */ for (int i = 0; i < 10; i++) { bucketList.add(new ArrayList<>()); } /* 外层循环:几轮排序 */ for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) { /* 遍历数组,投入桶中 */ for (int k : arr) { int num = (k % mod) / div; bucketList.get(num).add(k); } /* 从桶中取出 */ int index = 0; for (ArrayList<Integer> integers : bucketList) { for (Integer integer : integers) { arr[index++] = integer; } /* 清除桶,准备下一轮排序 */ integers.clear(); } } return arr; }
末尾表达歉意:所有动图都通过互联网搜索而来,如有冒犯请私信联系我。静态图有些是自己话的哈。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。