算法在手,天下我有。

一、算法分类

算法的时间复杂度和空间复杂度:

二、七大排序算法

(一)冒泡排序

1、基本思想

依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。

2、动态效果图

3、代码实现
//冒泡排序 private static void bubbleSort(int[] arr){ // 标识变量,表示是否进行过交换 boolean
flag = false; int temp = 0; for (int i = 0; i < arr.length-1; i++) { for (int j
= 0; j < arr.length-1-i; j++) { // 如果前面的数比后面的数大,则交换 if(arr[j]>arr[j+1]){ flag =
true; temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } //
在一趟排序中,一次交换都没有发生过 if(!flag){ break; } } }
4、速度测试

冒泡排序:120000数据,23秒

(二)选择排序

1、基本思想

(1)在序列中找到最小元素,放在第一个位置;

(2)从剩余未排序元素中继续寻找最小元素,放在第二个位置;

以此类推,直到排序完毕。

2、动态效果图

3、代码实现
//选择排序 public static void selectSort(int[] arr) { for (int i = 0; i <
arr.length - 1; i++) { int minIndex = i; int min = arr[minIndex]; for(int j = 1
+ i;j<arr.length;j++){ if(min > arr[j]){ min = arr[j]; minIndex = j; } }
arr[minIndex] = arr[i]; arr[i] = min; } }
4、速度测试

选择排序:120000数据,4秒

(三)插入排序

1、基本思想

把n个待排序的元素第一位看成有序表,其它的看成无序表,排序过程中,每次从无序表中取出一个数,依次与有序表中的数进行比较,插入到合适的位置。

2、动态效果图

3、代码实现
//插入排序 public static void insertSort(int[] arr ){ int insertVal = 0; int
insertIndex = 0; for (int i = 1; i < arr.length; i++) { //定义待插入的数 insertVal =
arr[i]; // 即arr[i]的前面这个数的下标 insertIndex = i - 1; // 给insertVal 找到插入的位置 // 说明 //
1. insertIndex >= 0 保证在给insertVal 找插入位置,不越界 // 2. insertVal < arr[insertIndex]
待插入的数,还没有找到插入位置 // 3. 就需要将 arr[insertIndex] 后移 while(insertIndex >= 0 &&
insertVal < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex];
insertIndex--; } // 当退出while循环时,说明插入的位置找到, insertIndex + 1 if(insertIndex + 1
!= i){ arr[insertIndex+1] = insertVal; } } }
4、速度测试

插入排序:120000数据,1秒

(四)希尔排序

1、基本思想

希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法也是冲破O(n²)的第一批算法之一。它与插入排序的不同之处在于,它会优先比较较远的元素。

2、效果图

3、代码实例

 希尔排序有两种方式。

①希尔排序(冒泡排序)
//希尔排序 // 使用逐步推导的方式来编写希尔排序 // 希尔排序时, 对有序序列在插入时采用交换法, // 思路(算法) ===> 代码 public
static void shellSort(int[] arr){ // 根据前面的逐步分析,使用循环处理 for(int step =
arr.length/2;step>0;step /= 2 ){ for (int i = step; i < arr.length; i++) { //
遍历各组中所有的元素(共step组,每组有个元素), 步长step for (int j = i - step; j >= 0; j -= step) {
// 如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + step]) { int temp = arr[j];
arr[j] = arr[j + step]; arr[j + step] = temp; } } } } }
速度测试:

冒泡法希尔排序:120000数据,11秒

②希尔排序(插入排序)
//对交换式的希尔排序进行优化->插入法 public static void shellSort2(int[] arr) { // 增量step,
并逐步的缩小增量 for (int step = arr.length / 2; step > 0; step /= 2) { //
从第step个元素,逐个对其所在的组进行直接插入排序 for (int i = step; i < arr.length; i++) { int j = i;
int temp = arr[j]; if(arr[j]<arr[j-step]){ while (j - step >=
0&&temp<arr[j-step]){ arr[j] = arr[j-step]; j -= step; } arr[j] = temp; } } }
速度测试:

插入法希尔排序:12000000数据,4秒,叹为观止

(五)快速排序

1、基本思想

通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录进行排序,以达到整个排序的过程。

2、效果图

3、算法描述

* 快速排序使用分治法把一个串分为两个子串;
* 找一个基准点,暂时选中间点为基准点;
* 重新排序数列,比基准值小的放在基准点前面,大的放在后面;
* 递归的把小于基准值的子数列和大于基准值的子数列排序;
4、代码实例
//快速排序 public static void quickSort(int[] arr,int left, int right) { int l =
left; //左下标 int r = right; //右下标 //pivot 中轴值 int pivot = arr[(left + right) /
2]; int temp = 0; //临时变量,作为交换时使用 //while循环的目的是让比pivot 值小放到左边 //比pivot 值大放到右边
while( l < r) { //在pivot的左边一直找,找到大于等于pivot值,才退出 while( arr[l] < pivot) { l +=
1; } //在pivot的右边一直找,找到小于等于pivot值,才退出 while(arr[r] > pivot) { r -= 1; } //如果l >=
r说明pivot 的左右两的值,已经按照左边全部是 //小于等于pivot值,右边全部是大于等于pivot值 if( l >= r) { break; }
//交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //如果交换完后,发现这个arr[l] ==
pivot值 相等 r--, 前移 if(arr[l] == pivot) { r -= 1; } //如果交换完后,发现这个arr[r] == pivot值
相等 l++, 后移 if(arr[r] == pivot) { l += 1; } } // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
if (l == r) { l += 1; r -= 1; } //向左递归 if(left < r) { quickSort(arr, left, r);
} //向右递归 if(right > l) { quickSort(arr, l, right); } }
5、速度测试

快速排序:12000000数据,1秒,逆天而行

(六)归并排序

1、基本思想

归并排序采用经典的分治策略,分治法将问题分成一些小的问题然后递归解决,则治的阶段就是将分的阶段得到的答案修补在一起,即分而治之。

2、效果图

 3、代码实现
//归并排序 public static void mergerSort(int[] arr,int left,int right,int[] temp){
if(left<right){ //中间索引 int middle = (left + right)/2; //向左递归进行分解
mergerSort(arr,left,middle,temp); //向右递归进行分解 mergerSort(arr,middle +
1,right,temp); //合并 merger(arr, left, middle, right, temp); } } //合并 public
static void merger(int[] arr,int left,int middle,int right,int[] temp){ int i =
left; // 初始化i, 左边有序序列的初始索引 int j = middle + 1; //初始化j, 右边有序序列的初始索引 int t = 0;
// 指向temp数组的当前索引 //先把左右两边(有序)的数据按照规则填充到temp数组 //直到左右两边的有序序列,有一边处理完毕为止 while (i
<= middle && j <= right) {//继续 //如果左边的有序序列的当前元素,小于等于右边有序序列的当前元素 //即将左边的当前元素,填充到
temp数组 //然后 t++, i++ if(arr[i] <= arr[j]){ temp[t] = arr[i]; t++; i++; }else {
//反之,将右边有序序列的当前元素,填充到temp数组 temp[t] = arr[j]; t++; j++; } }
//把有剩余数据的一边的数据依次全部填充到temp //左边的有序序列还有剩余的元素,就全部填充到temp while (i <= middle){
temp[t] = arr[i]; t++; i++; } //右边的有序序列还有剩余的元素,就全部填充到temp while (j <= right){
temp[t] = arr[j]; t++; j++; } //将temp数组的元素拷贝到arr //注意,并不是每次都拷贝所有 t = 0; int
tempLeft = left; // while (tempLeft <= right){ arr[tempLeft] = temp[t]; t++;
tempLeft++; } }
4、速度测试

归并排序:12000000数据,1秒,惊为天人

(七)基数排序

1、基本思想

将所有带比较数值统一为同样的数位长度,数据较短的数前面补0,然后从最低位开始依次进行依次排序,这样从最低位排序一直到最高位排序完成之后,数列就变成了一个有序序列。

2、动态效果图

3、代码实例
//基数排序 public static void radixSort(int arr[]){
System.out.println("基数排序,arr长度:"+arr.length); //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; }
} }
4、速度测试

基数排序:12000000数据,1秒,速度感人

技术
©2019-2020 Toolsou All rights reserved,
详解ubuntu14.04如何设置静态IPQCustomPlot系列(5)-实时动态曲线比尔·盖茨:疫情后彻底恢复正常可能要到2022年末华为认证HCIA-AI人工智能Python基础知识整理笔记百度、阿里、腾讯内部岗位级别和薪资结构,附带求职建议!Jsp+Ajax+Servlet+Mysql实现增删改查(一)2021年1月程序员工资统计,平均14915元Faster RCNN系列算法原理讲解(笔记)经典算法-递归(生兔子案例)