内容简介:为了准备面试,从2月开始将排序算法认认真真得刷了一遍,通过看书看视频,实践打代码,还有一部分的leetcode题,自己感觉也有点进步,将笔记记录总结发出来。不稳定,线性复杂度,完全二叉树。结点大于两边子树,arr[i]>arr[2i+1]&&a[i]>a[2i+2],升序使用这个
前言
为了准备面试,从2月开始将 排序 算法认认真真得刷了一遍,通过看书看视频,实践打代码,还有一部分的leetcode题,自己感觉也有点进步,将笔记记录总结发出来。
冒泡排序
- 该排序就是一种像泡泡浮到水面以后,将其挑选,这种浮出来的前提是就是或者是小的/大的先露头,将/小的大的检索出来。(根据从大到小或者反过来)
package src.datastructure; import java.util.Arrays; /** * @Author: yhy * @Time: 23:49 */ //时间复杂度O(n^2) public class DubbleSort { public static void main(String[] args) { int[] abc = {1,9,-2,40,33}; int temp = 0; boolean flag = false; //第一轮for,n个数都要参与比较。 for (int i = 0; i <abc.length-1 ; i++) { //第1个和其他的数进行比较。。再到第二个数与其他的 for (int j = 0; j < abc.length-1 ; j++) { //这里是升序排序 if (abc[j] > abc[j+1]) { flag = true; temp = abc[j]; abc[j] = abc[j+1]; abc[j+1] = temp; } } //这里优化了一些,减少了比较的次数,若排好序了,就直接跳出循环,输出结果 if (!flag) { break; }else { flag = false; } } System.out.println(Arrays.toString(abc)); } }
选择排序
- 先找个值假设作为最小值,进行该值以后的数与该值比较,小的就放在前面
package src.datastructure; import java.util.Arrays; /** * @Author: yhy * @Time: 15:30 * 选择排序 */ public class SelectSort { public static void main(String[] args) { int[] abc = {1,9,-2,40,33}; // 选择排序:选择一开始为最小的,然后每一次开始排序 // 也有最小值还有最小值的索引 for (int i = 0; i < abc.length; i++) { int min = abc[i]; int minIndex = i; for (int j = i+1; j < abc.length; j++) { if (min > abc[j]) { min = abc[j]; minIndex = j; abc[j] = abc[i]; } // 关键判断;要将原来的索引与min比较,若发生了交换,就将相对小的数放在前面去 if (minIndex != i) { abc[i] = min; } } } System.out.println(Arrays.toString(abc)); } }
插入排序
- 插入意思就是从无序区找值插到有序区去,所以取第一个值为有序区,等到有序区长度为n(数组长度)时候就成功排序。
package src.datastructure; import java.util.Arrays; /** * @Author: yhy * @Time: 15:30 */ public class InsertSort { public static void main(String[] args) { int[] abc = {1,9,-2,40,33}; // 插入排序,分为有序区,和无序区 // 和选择排序有那么一点相似, // 这里是将一部分定义为有,然后比较再选择插入的位置等 for (int i = 1; i < abc.length ; i++) { int insertIndex = i -1; int insertValue = abc[i]; // 这里的数组下标是可以等于0 while (insertIndex >= 0 && insertValue < abc[insertIndex]){ // 将大的值往后移,直到找到合适的插入位置 abc[insertIndex+1] = abc[insertIndex]; insertIndex--; } // 退出循环后,就说明插入的位置找到了 加入判断,如果没有进去while的话,就不用赋值,插入位置不变 if (insertIndex + 1 != i) { abc[insertIndex+1] = insertValue; } } System.out.println(Arrays.toString(abc)); } }
快速排序
- 一种双指针移动的排序,找个基准值
package src.datastructure; import java.util.Arrays; /** * @Author: yhy * @Time: 12:05 * 采用指针交换来做 */ public class QuickSort2 { public static void quickSort(int[] arr, int startIndex, int endIndex) { // 递归结束:startIndex 大于等于endIndex的时候 if (startIndex >= endIndex) { return; } // 得到基准元素位置 int pivotIndex = partition(arr, startIndex, endIndex); // 使用分治法递归数列的两部分 quickSort(arr, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex); } public static int partition(int[] arr, int startIndex, int endIndex) { // 这里的交换次数更少了 int pivot = arr[startIndex]; int left = startIndex; int right = endIndex; // 退出循环的时候,说明已经检索到中间位置了 while (left != right){ // 分别去找到左边和右边停止的指针 while (left < right && arr[right] > pivot){ right--; } while (left < right && arr[left] <= pivot){ left++; } // 然后进行交换 if (left < right) { int p = arr[left]; arr[left] = arr[right]; arr[right] = p; } } // 一轮交换已经结束 // pivot和指针重合点交换 // 将基准值放到所对应的位置 int p = arr[left]; arr[left] = arr[startIndex]; arr[startIndex] = p; return left; } public static void main(String[] args) { int[] arr = new int[]{4,2,3,6,15,7,1,9}; quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } }
希尔排序
- 希尔排序就是分组排序,将取一个间隔gap作为每次分的组数。
package src.datastructure; import java.util.Arrays; /** * @Author: yhy * @Time: 15:30 * 希尔排序 */ public class ShellSort { public static void main(String[] args) { int[] abc = {1,9,-2,40,33}; // 希尔排序,要进行分组排序,同时依据是gap长度除2,每一次进行交换 // 用到了插入排序和冒泡排序的感觉 // 这是分组 for (int gap = abc.length/2; gap > 0; gap /= 2) { // 这个for循环写法要注意 for (int i = gap; i < abc.length; i++) { int j = i; int temp = abc[j]; if (abc[j] < abc[j-gap]) { while (j - gap >= 0 && temp < abc[j-gap]){ abc[j] = abc[j-gap]; j -= gap; } //将相对小索引的值变为一开始的 abc[j] = temp; } } } System.out.println(Arrays.toString(abc)); } }
归并排序
- 利用了分治的思想,先分再合来排序。降低问题的难度,逐一突破。
package src.datastructure; import java.util.Arrays; /** * @Author: yhy * @Time: 0:06 */ public class MergeSort { public static void main(String[] args) { // 自顶向下的归并排序 int[] abc = {1, 9, -2, 40, 33, 6, 5}; int[] temp = new int[abc.length]; mergeSort(abc, 0, abc.length - 1, temp); System.out.println(Arrays.toString(abc)); } // 分加合 public static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = (left + right) / 2; //中间索引 //向左递归进行分解 mergeSort(arr, left, mid, temp); //向右递归进行分解 mergeSort(arr, mid + 1, right, temp); //合并 merge(arr, left, mid, right, temp); } } // 合方法 public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int leftStart = left; int rightStart = mid + 1; int i = 0; // 这里注意可以等于 while (leftStart <= mid && rightStart <= right) { if (arr[leftStart] >= arr[rightStart]) { temp[i++] = arr[rightStart++]; } else { temp[i++] = arr[leftStart++]; } } while (leftStart <= mid) { temp[i++] = arr[leftStart++]; } while (rightStart <= right) { temp[i++] = arr[rightStart++]; } // copy array i = 0; int tempLeft = left; while (tempLeft <= right) { arr[tempLeft++] = temp[i++]; } } }
基数排序
- 用到了十个桶,将每一个数据按照位数将其分割,百、十、个位数进行比较
package com.atguigu.sort; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; public class RadixSort { public static void main(String[] args) { int arr[] = { 53, 3, 542, 748, 14, 214}; // 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G // int[] arr = new int[8000000]; // for (int i = 0; i < 8000000; i++) { // arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数 // } radixSort(arr); System.out.println("基数排序后 " + Arrays.toString(arr)); } //基数排序方法 public static void radixSort(int[] arr) { //根据前面的推导过程,我们可以得到最终的基数排序代码 //1. 得到数组中最大的数的位数 int max = arr[0]; //假设第一数就是最大数 for(int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } //得到最大数是几位数 int maxLength = (max + "").length(); //定义一个二维数组,表示10个桶, 每个桶就是一个一维数组 //说明 //1. 二维数组包含10个一维数组 //2. 为了防止在放入数的时候,数据溢出,则每个一维数组(桶),大小定为arr.length //3. 名明确,基数排序是使用空间换时间的经典算法 int[][] bucket = new int[10][arr.length]; //为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数 //可以这里理解 //比如:bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数 int[] bucketElementCounts = new int[10]; //这里我们使用循环将代码处理 for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) { //(针对每个元素的对应位进行排序处理), 第一次是个位,第二次是十位,第三次是百位.. for(int j = 0; j < arr.length; j++) { //取出每个元素的对应位的值 int digitOfElement = arr[j] / n % 10; //放入到对应的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来数组) int index = 0; //遍历每一桶,并将桶中是数据,放入到原数组 for(int k = 0; k < bucketElementCounts.length; k++) { //如果桶中,有数据,我们才放入到原数组 if(bucketElementCounts[k] != 0) { //循环该桶即第k个桶(即第k个一维数组), 放入 for(int l = 0; l < bucketElementCounts[k]; l++) { //取出元素放入到arr arr[index++] = bucket[k][l]; } } //第i+1轮处理后,需要将每个 bucketElementCounts[k] = 0 !!!! bucketElementCounts[k] = 0; } } } }
- leetcode 347题
package src.datastructure; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * @Author: yhy * @Time: 14:37 * leetcode #347 * 用到了桶排序的思想 */ public class BucketSort { // Given [1,1,1,2,2,3] and k = 2, return [1,2]. public static void main(String[] args) { int[] arr = new int[]{1, 1, 1, 2, 2, 3}; int[] a = bucketsort(arr); System.out.println(Arrays.toString(a)); System.out.println(maxReturn(a,2)); } // 传入数组,返回数组 public static int[] bucketsort(int[] arr){ // 定义一个桶 int[] bucket = new int[10]; for (int val: arr ) { bucket[val]++; } return bucket; } private static List maxReturn(int[] arr,int k){ int max = arr[0]; List<Integer> list = new ArrayList<>(); while (k >0) { for (int i = 1; i < arr.length; i++) { if (max < arr[i]) { max = arr[i]; arr[i] = 0; list.add(i); } } max = 0; k--; } return list; } }
堆排序
不稳定,线性复杂度,完全二叉树。
大顶堆
结点大于两边子树,arr[i]>arr[2i+1]&&a[i]>a[2i+2],升序使用这个
package src.datastructure.sort; import java.util.Arrays; /** * @Author: yhy * @Date: 2020/3/19 * @Time: 12:30 */ public class HeapSort { public static void main(String[] args) { int[] arr = {12, 3, 63, 6, 8}; heapsort(arr); } public static void heapsort(int[] arr) { int temp = 0; System.out.println("堆排序"); //找到第一个大顶堆结构,然后才可以进行下面的代码 for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, arr.length); } System.out.println(Arrays.toString(arr)); //交换数据,数组排序 调整堆结构+交换堆顶元素与末尾元素 for (int i = arr.length - 1; i > 0; i--) { temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, i); } System.out.println("排序后的" + Arrays.toString(arr)); } public static void adjustHeap(int[] arr, int i, int length) { //不断调整,弄个大顶堆 //后面要进行交换 int temp = arr[i]; //寻找非叶子节点 最后的条件表示左子节点还可以往下寻找 for (int j = i * 2 + 1; j < length; j = j * 2 + 1) { //左右节点的比较 if (j + 1 < length && arr[j] < arr[j + 1]) { j++; } if (arr[j] > temp) { arr[i] = arr[j]; i = j; } else { break; } } arr[i] = temp; } }
小顶堆
结点小于两边子树
思想(借助树的结构完成排序)
- 将待排序序列构造成一个大顶堆
- 此时序列的最大值就是堆顶的根节点
- 将其与数组末尾元素交换,这样构造数组的最大值在右边
- 再将n-1个元素重新构造一个堆,这样就会得到n个元素的次小值,反复进行就可以得到一个有序的数组,完成排序
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 算法之常见排序算法-冒泡排序、归并排序、快速排序
- 排序算法之冒泡排序改进算法
- 快速排序算法,C语言快速排序算法深入剖析
- 排序算法下——桶排序、计数排序和基数排序
- 数据结构和算法面试题系列—排序算法之快速排序
- 数据结构和算法面试题系列—排序算法之基础排序
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
菜鸟侦探挑战数据分析
[日] 石田基广 / 支鹏浩 / 人民邮电出版社 / 2017-1 / 42
本书以小说的形式展开,讲述了主人公俵太从大学文科专业毕业后进入征信所,从零开始学习数据分析的故事。书中以主人公就职的征信所所在的商业街为舞台,选取贴近生活的案例,将平均值、t检验、卡方检验、相关、回归分析、文本挖掘以及时间序列分析等数据分析的基础知识融入到了生动有趣的侦探故事中,讲解由浅入深、寓教于乐,没有深奥的理论和晦涩的术语,同时提供了大量实际数据,使用免费自由软件RStudio引领读者进一步......一起来看看 《菜鸟侦探挑战数据分析》 这本书的介绍吧!