iterator的使用+求数组中的第n大值+十大经典排序算法

一、iterator的用法

1、删除0到101中可以被2、被3、被5整除的数字

（1）方法一：使用for循环遍历删除

List<Integer> list = new ArrayList<>();// 将0-101存入listfor(int i = 0;i <= 100;i++){list.add(i);}System.out.println(list);// 从list中删除能被2、被3、被5整除的数字for(int i = 0;i < list.size();i++){int num = list.get(i);if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0){list.remove(Integer.valueOf(num));// 删除对象类型 new Integer(num)i--;}}System.out.println(list);

（2）方法二：使用iterator删除

 List<Integer> list = new ArrayList<>();// 将0-101存入listfor(int i = 0;i <= 100;i++){list.add(i);}System.out.println(list);// 从list中删除能被2、被3、被5整除的数字Iterator<Integer> iterator = list.iterator();// iterator会遍历到每一个元素while(iterator.hasNext()){// 判断下一个元素是否存在int num = iterator.next();// 获取下一个元素if(num %2 == 0 || num % 3 == 0 || num % 5 == 0){iterator.remove();// 删除下一个元素}}System.out.println(list);

二、求一个数组中的第n大值（n为2或者3）

1、求一个数组中的第二大值（不能使用排序）

/*** 求一个数组中的第二大数（不能使用排序）*/
public class SecondMax {public int secondMax(int[] nums){// 拿到一个值作为最大值，拿到一个值作为第二大值int max = nums[0];int second = nums[1];if(second > max){int t = max;max = second;second = t;}// 从第三个数开始，不断调整second和maxfor(int i = 2;i < nums.length;i++){if(nums[i] > max){second = max;max = nums[i];}else if(nums[i] > second){second = nums[i];}}return second;}public static void main(String[] args) {int[] nums = {7,9,5,6,8};System.out.println(new SecondMax().secondMax(nums));}
}

2、求一个数组中的第三大值（不能使用排序）

/*** 求一个数组中的第三大值*/
public class ThirdMax {public int thirdMax(int[] nums) {Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());nums = set.stream().mapToInt(Integer::intValue).toArray();// 1个元素if(nums.length == 1){return nums[0];}// 2个元素if(nums.length == 2){return nums[0] > nums[1] ? nums[0] : nums[1];}// 3个及三个元素// 假设获取到第一大值，第二大值，第三大值int max = nums[0];int second = nums[1];int third = nums[2];if(second > max){int t = max;max = second;second = t;}if(third > max){int t = max;max = third;third = t;}if(third > second){int t = second;second = third;third = t;}for(int i = 3;i < nums.length;i++){if(nums[i] > max){third = second;second = max;max = nums[i];}else if(nums[i] > second){third = second;second = nums[i];}else if(nums[i] > third){third = nums[i];}}return  third;}public static void main(String[] args) {int[] nums = {7,9,5,6,8};System.out.println(new ThirdMax().thirdMax(nums));}
}

三、冒泡排序

1、基本思想

将一个数组中的最大元素不断放在数组中的最后一个位置

2、代码实现

/*** 冒泡排序*/
public class BubbleSort {/*** 交换数组中两个指定位置的数组元素的值* @param i* @param j* @param nums*/private void swap(int i,int j,int[] nums){int t = nums[i];nums[i] = nums[j];nums[j] = t;}public void bubbleSort(int[] nums){for(int i = 0;i < nums.length - 1;i++){// 处理length - 1次数组for(int j = 0;j <= nums.length - 2 - i;j++){// 处理一次数组 将数组中最大值移动到数组最后一个位置上if(nums[j] > nums[j+1]){swap(j,j + 1, nums);}}}}public static void main(String[] args) {int[] nums = {3,2,1,6,5,4};new BubbleSort().bubbleSort(nums);System.out.println(Arrays.toString(nums));}
}

3、存在问题及改进方式

（1）存在问题：数组【1,2,3,4,5,6】也要进行一次冒泡排序

（2）改进方式：

public void bubbleSort(int[] nums){for(int i = 0;i < nums.length - 1;i++){// 处理length - 1次数组boolean flag = false;for(int j = 0;j <= nums.length - 2 - i;j++){// 处理一次数组 将数组中最大值移动到数组最后一个位置上if(nums[j] > nums[j+1]){swap(j,j + 1, nums);flag = true;}}// 没有一次交换，则flag为false，则nums为升序，则跳出外层循环if(!flag){break;}}}

四、选择排序

1、基本思想

不断将数组中的最大元素放在第一个位置

2、代码实现

/*** 选择排序*/
public class SelectSort {/*** 交换数组中两个指定位置的数组元素的值* @param i* @param j* @param nums*/private void swap(int i,int j,int[] nums){int t = nums[i];nums[i] = nums[j];nums[j] = t;}/*** 选择排序* @param nums*/public void selectSort(int[] nums){for(int i = 0;i < nums.length - 1;i++){// 处理length - 1次数组int max = i;// 遍历当前数组，更新maxfor(int j = i+1;j < nums.length;j++){if(nums[j] > nums[max]){max = j;}}swap(max,i,nums);}}public static void main(String[] args) {int[] nums = {3,2,1,6,5,4};new SelectSort().selectSort(nums);System.out.println(Arrays.toString(nums));}
}

五、插入排序

/*** 插入排序 核心思想：将数组分为有序区和无序区，有序区默认为第一个元素，从无序区中不断取出第一个元素作为待* 插入元素，对有序区中的元素从后向前进行查找，找到第一个比待插入元素小的元素，将待插入元素插入到该元素后* 面的位置上，如果在有序区中没有找到比待插入元素小的元素，将待插入元素插入到有序区中第一个元素的位置上*/
public class InsertSort {public void sort(int[] arr){if(arr == null || arr.length == 0){return;}int length = arr.length;for(int i = 1;i < length;i++){// 取出有序区中的元素int t = arr[i];// 保存有序区中的元素int j = i - 1;// 保存无序区中的最后一个元素while (j>=0){if(arr[j] > t){arr[j+1] = arr[j];j--;}else {// 找到第一个较小元素/*arr[j+1] = t;*/break;}}// 没找到第一个较小元素arr[j+1] = t;}}public static void main(String[] args) {int[] arr = {3,7,5,8,2,4,6};System.out.println("排序前的数组:" + Arrays.toString(arr));new InsertSort().sort(arr);System.out.println("排序后的数组:" + Arrays.toString(arr));}
}

六、希尔排序

/*** 希尔排序 核心思想：插入排序，先保证数据部分有序，再将部分有序的数组通过插入排序合并成一个有序数组*/
public class ShellSort {public void sort(int[] arr){// 入参判断if(arr == null || arr.length == 0){return;}int length = arr.length;// 确定步数for(int step = length / 2;step >= 1;step= step / 2){// 按照步数进行分组，每组两个元素for(int i = step;i < arr.length;i++){// 对每一组元素进行插入排序int j = i - step;int insertVal = arr[i];while (j>=0){if(arr[j] > insertVal){arr[j+step] = arr[j];j -= step;}else{break;}}arr[j+step] = insertVal;}}}public static void main(String[] args) {int[] arr = {3,7,5,8,2,4,6};System.out.println("排序前的数组:" + Arrays.toString(arr));new ShellSort().sort(arr);System.out.println("排序后的数组:" + Arrays.toString(arr));}
}

七、归并排序

/*** 归并排序 核心思想:归并排序是建立在归并操作上的排序算法，该算法是分治法的一个典型应用*/
public class MergeSort {public static int[] sort(int[] arr){// 入参判断if(arr == null || arr.length < 2){return arr;}int mid = arr.length / 2;int[] leftArr = Arrays.copyOfRange(arr, 0, mid);// 对一个数组进行范围性复制，得到一个新的数组int[] rightArr = Arrays.copyOfRange(arr,mid, arr.length);return merge(sort(leftArr),sort(rightArr));}/*** 辅助方法：将两个有序数组合并为一个有序数组* @param nums1* @param nums2*/public static int[] merge(int[] nums1,int[] nums2){// 入参判断if(nums1 == null || nums1.length == 0){return nums2;}if(nums2 == null || nums2.length == 0){return nums1;}int[] result = new int[nums1.length + nums2.length];int i = 0;int j = 0;int k = 0;while (i < nums1.length && j < nums2.length){if(nums1[i] < nums2[j]){result[k++] = nums1[i++];}else {result[k++] = nums2[j++];}}while (i < nums1.length){result[k++] = nums1[i++];}while (j < nums2.length){result[k++] = nums2[j++];}return result;}public static void main(String[] args) {int[] arr = {3,7,5,8,2,4,6};System.out.println("排序前的数组:" + Arrays.toString(arr));System.out.println("排序后的数组:" + Arrays.toString(sort(arr)));}
}

八、快速排序

1、算法步骤

（1）从数列中挑出一个元素作为基准(pivot)，一般选择第一个元素作为数列的基准

（2）对数列进行排序，将所有比基准小的元素放在基准前面，将所有比基准大的放在基准后面，和基准相等的可以放在任意一边。在这个分区退出之后，该基准就位于数列的中间位置。(2)操作被称为分区（partition）操作。

（3）递归地(recursive)对小于基准的元素的子序列和大于基准的元素的子序列进行排序

2、算法实现

/*** 快速排序*/
public class FastSort {/*** 对数组指定区间进行快速排序* @param arr* @param left* @param right*/public static void sort(int[] arr,int left,int right){// 入参判断if(arr == null || arr.length < 2){return ;}// 递归到底的情况if(left>=right){return;}// 递归操作// 1、确定基准int pivot = arr[left];// 确定基准// 2、将区间数组中比基准小的元素放在基准前面，比基准大的元素放在基准后面，重复此操作int i = left;int j = right;while (i<j){// 从区间数组右边最后一个元素开始找，找到比基准小的第一个元素放在基准前面while (i<j && arr[j]>pivot){j--;}if(i<j){arr[i] = arr[j];i++;}// 从区间数组左边第一个元素开始找，找到比基准大的第一个元素放在基准后面while (i<j && arr[i]<pivot){i++;}if(i<j){arr[j] = arr[i];j--;}}// 将基准元素放到分区位置arr[i] = pivot;// 3、对区间数组的左右子区间分别进行快速排序sort(arr, left, i-1);sort(arr, i+1, right);}public static void main(String[] args) {int[] nums = {7,4,8,2,1,0,9,6,5,3};System.out.println("排序前的数组:"+ Arrays.toString(nums));sort(nums, 0, nums.length - 1);System.out.println("排序前的数组:"+ Arrays.toString(nums));}
}

3、复杂度分析

（1）快速排序的最坏情况的时间复杂度是 $O(n^{2})$ ，比如顺序数列的快排

（2）快速排序的平摊期望时间是 $O(nlog_{2}^{n})$ ，且 $O(nlog_{2}^{n})$ 隐藏的常数因子比复杂度稳定等于 $O(log_{2}^{n})$ 的归并排序要小很多。因此，对于绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序

九、堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一种等效于完全二叉树的数据结构，满足以下性质，即子节点的键值或索引总是小于（或者大于）他的父节点。堆排序是利用了堆概念的选择排序。有两种实现方法：

大顶堆：每个节点的值都大于或者等于其子节点的值，可用于实现升序排列的堆排序

小顶堆：每个节点的值都小于或者等于其子节点的值，可用于实现降序排列的堆排序

1、算法步骤（升序排序）

（1）使用heapify方法堆化数组

（2）交换堆首和堆尾元素

（3）调用swim()方法，使得除过堆尾元素的树满足最大堆的性质

（4）重复步骤(2)，直到堆中只有一个元素

2、算法实现

/*** 堆排序*/
public class HeapSort {/*** 获取当前节点的父节点的索引* @param index* @return*/private static int getParentIndex(int index){if(index == 0){return -1;// 特殊表示}return (index - 1) / 2;}/*** 获取当前节点的左孩子节点的索引* @param index* @return*/private static int getLeftIndex(int index){return index * 2 + 1;}/*** 对索引为compaerIndex的节点执行下沉操作* @param compareIndex 索引* @param arr 数组* @param length 数组长度*/private static void swim(int compareIndex,int[] arr,int length){int compareVal = arr[compareIndex];// 记录当比较节点的索引int curIndex = compareIndex;// 获取左孩子节点的索引int leftIndex = getLeftIndex(curIndex);// 左孩子存在while (leftIndex < length){// 获取左右孩子节点中优先级较高节点的索引int changeIndex = leftIndex;int rightIndex = leftIndex + 1;if(rightIndex < length && arr[rightIndex] > arr[leftIndex]){changeIndex = rightIndex;}// 与当前节点比较，如果当前节点的优先级低于交换节点，则交换当前节点和交换节点if(compareVal < arr[changeIndex]){arr[curIndex] = arr[changeIndex];curIndex = changeIndex;leftIndex = getLeftIndex(curIndex);}else{break;}}arr[curIndex] = compareVal;}/*** 堆化数组,使得数组具备堆的性质* @param arr*/private static void heapify(int[] arr){// 入参判断if(arr == null || arr.length == 0){return;}int lastIndex = arr.length - 1;// 获取最后一个节点的父节点的索引int lastParentIndex = getParentIndex(lastIndex);// 从该节点开始向前到堆顶节点进行进行下沉for(int i = lastParentIndex;i >= 0;i--){swim(i,arr,arr.length);}}/*** 交换数组arr中第i个元素和第j个元素的位置* @param i* @param j* @param arr*/private static void swap(int i,int j,int[] arr){int t = arr[i];arr[i] = arr[j];arr[j] = t;}public static void sort(int[] arr){heapify(arr);if(arr == null || arr.length == 0){return;}// 堆排序for(int i = arr.length - 1;i > 0;i--){// 1、将堆中第一个元素与最后一个元素交换位置swap(0,i,arr);// 2、对堆顶元素做下沉操作swim(0, arr, i);}}public static void main(String[] args) {int[] arr = {3,10,12,5,6,98,4,5,34,25,36,75,10};System.out.println("排序前的数组:" + Arrays.toString(arr));sort(arr);System.out.println("排序后的数组:" + Arrays.toString(arr));}
}

十、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的新数组空间中。计数排序是一种线性时间复杂度的排序，要求输入的数据必须是确定范围的整数

1、计数排序的特征

（1）当输入的元素是n个0到k之间的整数时，它的运行时间是 $O(n+k)$ 。计数排序不是比较排序，排序的速度快于任何比较排序算法

（2）由于用来计数的Hash数组的长度取决于待排序数组中数据的范围（等于待排序数组中的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要很大的时间和内存

（3）通俗地理解，例如有10个年龄不同的人，统计出有5个人年龄比A小，那A的年龄就排在第6位，使用这个方法就可以得到其他每个人的位置，也就排好了序。当然，年龄有重复时也需要进行特殊处理（为了保证稳定性），这就是为什么最后要反向填充待排序数组，以及将每个数字的统计减去1的原因

2、算法步骤

（1）找出待排序的数组中的最大元素

（2）统计待排序数组中值为i的元素出现的次数，存入数组Hash的第i项

（3）反向填充待排序数组，依次将Hash数组中的每一个元素i放在待排序数组的第index位置上，放Hash[i]次

3、算法实现

/*** 计数排序*/
public class CountSort {private static int getMax(int[] arr){return Arrays.stream(arr).max().getAsInt();}public static  void sort(int[] arr){// 入参判断if(arr == null || arr.length < 2){return;}// 计数排序// 1、找到待排序数组中的最大元素int max = getMax(arr);int[] hash = new int[max + 1];// 2、统计待排序数组中每个元素i出现的次数，并存入hash数组中的第i项Arrays.stream(arr).forEach(item->{hash[item]++;});// 3、反向填充待排序数组int index = 0;for(int i = 0;i < hash.length;i++){int count = hash[i];while (count-- > 0){arr[index++]=i;}}}public static void main(String[] args) {int[] arr = {3,10,12,5,6,98,4,5,34,25,36,75,10};System.out.println("排序前的数组:" + Arrays.toString(arr));sort(arr);System.out.println("排序后的数组:" + Arrays.toString(arr));}
}

4、适用范围

计数排序适用于数据范围比较小的数组，且数组中的元素必须是非负整数

5、稳定排序和不稳定排序

（1）区别：相同元素的相对位置是否发生了改变，没改变就是稳定排序，改变了就是非稳定排序

（2）插入排序可以是稳定排序，也可以不是稳定排序，但一般来讲不是稳定排序

（3）计数排序既可以是稳定排序又可以是非稳定排序，但一般来讲是稳定排序

（4）快速排序不是稳定排序

十一、桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否取决于映射函数的确定。为了使得桶排序更加高效，我们需要做到以下两点：

（一）在额外空间充足的情况下，尽可能增大桶的数量

（二）所使用的映射函数能够将输入的N个数据均匀分配到k个桶中

（三）对于同种元素的排序，选择何种比较排序算法对桶排序性能的影响至关重要

1、算法实现

/*** 桶排序 核心思想：将在指定范围内的一堆数据按照映射关系放入不同的桶中，对每个桶进行排序，最终通过会回填的方式得到一个有序* 的数列* 关键点：1、确定桶的数目 2、将元素尽量均匀地放在每个桶中*/
public class BucketSort {/*** 对数组进行排序* 数组中的元素的范围是[0,150)* @param arr*/public static void sort(int[] arr){// 入参判断if(arr == null || arr.length == 0){return;}// 1、确定桶的个数int bucketCount = 15;// 2、确定元素与桶的映射关系(0-9,10-19,...,140-149)List<Integer>[] buckets = new List[15];for(int i = 0;i < buckets.length;i++){buckets[i] = new ArrayList<>();}// 3、将元素放入桶中Arrays.stream(arr).forEach(item->{buckets[item/10].add(item);});// 4、对每个桶进行排序for(int i = 0;i < buckets.length;i++){buckets[i].sort(Comparator.comparingInt(o -> o));}// 5、回填数组int index = 0;for(int i = 0;i < buckets.length;i++){List<Integer> bucket = buckets[i];while (bucket.size() > 0){arr[index++] = bucket.remove(0);}}}public static void main(String[] args) {int[] arr = {3,10,12,5,6,98,123,114,125,101,100,12,146,4,5,34,25,36,75,10};System.out.println("排序前的数组:" + Arrays.toString(arr));sort(arr);System.out.println("排序后的数组:" + Arrays.toString(arr));}
}

2、算法分析

（1）最快的情况

输入的数据都被均匀地分配到每一个桶中

（2）最慢的情况

输入的数据都被分配到了一个桶中

（3）桶中元素示意图

十二、基数排序

基数排序的原理是将整数按位数分割成不同的数字，然后按每个位数分别进行比较。基数排序的方式可以采用LSD或MSD。

MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序

LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

1、使用LSD实现基数排序算法

/*** 基数排序 核心思想：按位取余放桶中，对桶排序再回填*/
public class RadixSort {/*** 获取arr中的最大元素* @param arr* @return*/public static int getMax(int[] arr){return Arrays.stream(arr).max().getAsInt();}/*** 获取num的位数* @param num* @return*/public static int getDigit(int num){int digit = 1;while(num/10 != 0){digit++;num = num / 10;}return digit;}public static void sort(int[] arr){// 入参判断if(arr == null || arr.length == 0){return;}// 获取arr中最大元素的位数int max = getMax(arr);int maxDigit = getDigit(max);int dev = 1;for(int k = 0;k < maxDigit;k++){// 桶排序int mod = 10;// 创建桶int bucketCount = 10;List<Integer>[] buckets = new List[bucketCount];for(int i = 0;i < buckets.length;i++){buckets[i] = new ArrayList<>();}// 按个位取余放入对应的桶中for(int i = 0;i < arr.length;i++){buckets[arr[i]/dev%mod].add(arr[i]);}// 对每个桶进行排序for(int i = 0;i < buckets.length;i++){buckets[i].sort((o1, o2) -> o1 - o2);}// 回填目标数组int index = 0;for(int i = 0;i < buckets.length;i++){List<Integer> bucket = buckets[i];while (bucket.size() > 0){arr[index++] = bucket.remove(0);}}dev = dev * 10;}}public static void main(String[] args) {int[] arr = {3,10,12,526,6,98,123,114,1125,101,100,12,146,4,5,34,25,36,75,10};System.out.println("排序前的数组:" + Arrays.toString(arr));sort(arr);System.out.println("排序后的数组:" + Arrays.toString(arr));}
}