算法在手，天下我有。
一、算法分类
算法的时间复杂度和空间复杂度：
二、七大排序算法
（一）冒泡排序
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秒，速度感人
转载：https://blog.csdn.net/guorui_java/article/details/106270186
查看评论