排序算法的介绍
排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。
排序的分类：
内部排序: 指将需要处理的所有数据都加载到内部存储器(内存)中进行排序。外部排序法： 数据量过大，无法全部加载到内存中，需要借助外部存储(文件等)进行排序。常见的排序算法分类(见下图):
其中直接插入排序，简单选择排序，冒泡排序最常见基数排序也是桶排序的一种
冒泡排序
基本介绍
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
优化：
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)
演示冒泡过程的例子(图解)
小结上面的图解过程:
1.一共进行数组的大小-1 次大的循环
每一趟排序的次数在逐渐的减少如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。这个就是优化
交换条件： if (arr[j] > arr[j + 1])
交换过程：
把a[j]保存起来：temp = arr[j];j+1位置向左移：arr[j] = arr[j + 1];j+1位置的元素变成：arr[j + 1]= temp;
优化 if (!flag) { // 在一趟排序中，一次交换都没有发生过 break; } else { flag = false; // 重置flag!!!, 进行下次判断 }
代码实现
import java
.text
.SimpleDateFormat
;
import java
.util
.Arrays
;
import java
.util
.Date
;
public class BubbleSort {
public static void main(String
[] args
) {
int[] arr
= new int[80000];
for(int i
=0; i
< 80000;i
++) {
arr
[i
] = (int)(Math
.random() * 8000000);
}
Date data1
= new Date();
SimpleDateFormat simpleDateFormat
= new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str
= simpleDateFormat
.format(data1
);
System
.out
.println("排序前的时间是=" + date1Str
);
bubbleSort(arr
);
Date data2
= new Date();
String date2Str
= simpleDateFormat
.format(data2
);
System
.out
.println("排序后的时间是=" + date2Str
);
}
public static void bubbleSort(int[] arr
) {
int temp
= 0;
boolean flag
= false;
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;
} else {
flag
= false;
}
}
}
}
问题：
问题一：第一次是j < arr.length - 1的原因 for (int j = 0; j < arr.length - 1 - i; j++) { //因为比较的是j和j+1所以j<arr.length-1，j< arr.length则溢出 问题二：为什么是 j < arr.length - 1 - i最后为什么减i 第一趟排序，就是将第一大的数排在倒数第一位 第二趟排序，就是将第二大的数排在倒数第二位 第一趟后最后一位确定了不用再遍历到最后一位了，可以减少循环次数。
选择排序
基本介绍
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
选择排序思想:
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是： 第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换， 第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换， 第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…， 第i 次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1 次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1 次，得到一个按排序码从小到大排列的有序序列。
选择排序思路分析图:
对一个数组的选择排序再进行讲解
原始的数组 ： 101, 34, 119, 1 第一轮排序 : 1, 34, 119, 101 第二轮排序 : 1, 34, 119, 101 第三轮排序 : 1, 34, 101, 119 说明：
选择排序一共有 数组大小 - 1 轮排序每1轮排序，又是一个循环, 循环的规则(代码) 2.1先假定当前这个数是最小数 2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标 2.3 当遍历到数组的最后时，就得到本轮最小数和下标 2.4 交换 [ 交换到数组-1第一个数组]
简单的说：
假如：int [] arr = {101, 34, 119, 1};
先定义：arr[i]是需要交换的指针min指向最小的数和指针的下标minIndex先假设最小的就是arr[i]，min指arr[i]，最后一次不用指，因为已经是最后一个了。 for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; int min = arr[i]; }又一个for循环：j也就是min的下一个,i+1,他就会在剩下的i+1至arr.length中找最小的重置min，minIndex（假如是最后一个则，minlndex=4,min=1） for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) { // 说明假定的最小值，并不是最小 min = arr[j]; // 重置min minIndex = j; // 重置minIndex }交换： 3.1： arr[minIndex] = arr[i];（第一个换到最后一个去即数组变成：{1，34，119，101} 3.2 ： arr[i] = min;（第一个是min=1）优化： 假如minlndex本来就是第一个了就不用交换了所以不是i才进行交换 if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = min; }
选择排序应用实例:
有一群牛, 颜值分别是101, 34, 119, 1 请使用选择排序从低到高进行排序[101, 34, 119, 1]
代码实现
import java
.text
.SimpleDateFormat
;
import java
.util
.Arrays
;
import java
.util
.Date
;
public class SelectSort {
public static void main(String
[] args
) {
int[] arr
= new int[80000];
for (int i
= 0; i
< 80000; i
++) {
arr
[i
] = (int) (Math
.random() * 8000000);
}
System
.out
.println("排序前");
Date data1
= new Date();
SimpleDateFormat simpleDateFormat
= new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str
= simpleDateFormat
.format(data1
);
System
.out
.println("排序前的时间是=" + date1Str
);
selectSort(arr
);
Date data2
= new Date();
String date2Str
= simpleDateFormat
.format(data2
);
System
.out
.println("排序前的时间是=" + date2Str
);
}
public static void selectSort(int[] arr
) {
for (int i
= 0; i
< arr
.length
- 1; i
++) {
int minIndex
= i
;
int min
= arr
[i
];
for (int j
= i
+ 1; j
< arr
.length
; j
++) {
if (min
> arr
[j
]) {
min
= arr
[j
];
minIndex
= j
;
}
}
if (minIndex
!= i
) {
arr
[minIndex
] = arr
[i
];
arr
[i
] = min
;
}
}
}
}
问题：
如果改为降序 if (min > arr[j])改为if (min <carr[j])即可
上面的选择排序的时间比冒泡排序短 虽然他们时间复杂度一样但是选择排序for循环里面的语句少很多，而且是if语句，很多情况下不用执行
插入排序
插入排序法介绍:
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
插入排序法思想:
插入排序（Insertion Sorting）的基本思想是：把n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
插入排序思路图:
思路分析
标准分析. 有序表在左边，无序表在右边。 insertVal (temp)是无序表的第一个指针指向a[i] insertIndex(j)有序表倒数第一个指针的下标
第一次： temp指针在第二个也就是arr[1]这个位置， j为0，arr[j]看成一个有序表循环（找不到插入位置）j指的位置大于temp： while( j一定要>=0，temp< arr[j]，j- -(有序表内查找）); arr[j + 1] = arr[j]（意思就是有序列表数组的元素向右移动）当找到位置的时候插入：j指的位置小于temp了，所以j后面一位就可以是temp了： arr[j+ 1] = temp;优化：要赋值插入的数字本来就在j后面一位即if(insertIndex + 1 = i)，不用赋值了直接下轮循环如果不是 if(insertIndex + 1 != i) { arr[insertIndex + 1] = insertVal; }
插入排序法应用实例:
有一群小牛, 考试成绩分别是101, 34, 119, 1 请从小到大排序
代码实现：
import java
.text
.SimpleDateFormat
;
import java
.util
.Arrays
;
import java
.util
.Date
;
public class InsertSort {
public static void main(String
[] args
) {
int[] arr
= new int[80000];
for (int i
= 0; i
< 80000; i
++) {
arr
[i
] = (int) (Math
.random() * 8000000);
}
System
.out
.println("插入排序前");
Date data1
= new Date();
SimpleDateFormat simpleDateFormat
= new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str
= simpleDateFormat
.format(data1
);
System
.out
.println("排序前的时间是=" + date1Str
);
insertSort(arr
);
Date data2
= new Date();
String date2Str
= simpleDateFormat
.format(data2
);
System
.out
.println("排序前的时间是=" + date2Str
);
}
public static void insertSort(int[] arr
) {
int insertVal
= 0;
int insertIndex
= 0;
for(int i
= 1; i
< arr
.length
; i
++) {
insertVal
= arr
[i
];
insertIndex
= i
- 1;
while (insertIndex
>= 0 && insertVal
< arr
[insertIndex
]) {
arr
[insertIndex
+ 1] = arr
[insertIndex
];
insertIndex
--;
}
if(insertIndex
+ 1 != i
) {
arr
[insertIndex
+ 1] = insertVal
;
}
}
}
}
for循环版本
void StraightSort(int *arr
,int len
)
{
int tmp
;
int i
;
int j
;
for (i
= 1;i
< len
;i
++)
{
tmp
= arr
[i
];
for (j
= i
- 1;j
>= 0 && arr
[j
] > tmp
;j
--)
{
arr
[j
+ 1] = arr
[j
];
}
arr
[j
+ 1] = tmp
;
}
}
问题：
降序的时候 while (insertIndex >= 0 && insertVal < arr[insertIndex])改为while (insertIndex >= 0 && insertVal >arr[insertIndex])
insertIndex一定要>=0 一定要在insertIndex一定要>=0的情况下减减，不然要插入的数字在第一个的时候也就是arr[0]就会出错，因为insertIndex会一直减下去
注意：
for (int j = 0; j < arr.length-1; j++)中 j < arr.length-1代表arr[j]倒数第二位 for (int j = 0; j < arr.length; j++)中 j < arr.length代表arr[j]倒数第一位
