?
分类：
?一、冒泡排序：（平均时间复杂度：O(n^2)）
? ? ? ? 1、基本思想：通过对待排序列从前向后，依次比较相邻元素的值，若逆序则交换，使较大的元素逐渐从前移向后部，类似水底下的气泡一样逐渐往上冒，每进行完一轮排序，都会使得排序序列最后一个数为最大的。
? ? ? ??2、算法优化：在排序的过程中，如果一趟比较下来的没有进行过数交换，则说明当前的序列已经有序了，不用再进行接下来的排序。因此在排序过程中设置一个标志flag判断元素是否进行过交换，可以适当优化。
? ? ? ? 3、演示冒泡排序过程的例子：
????????
? ? ? ? ?小结上述例子：
? ? ? ? ? （1）一共进行数组的长度 - 1次排序循环
? ? ? ? ? （2）每一趟排序的次数都在不断的减少
? ? ? ? ? （3）如果在某一躺发现没有交换，则可提前结束
? ? ? ? ?4、代码如下：
????????
?
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 + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
if(!flag){
break;
}else{
flag = false;
}
}
}
?? ? ? ? 解释：（1）外层循环控制的是循环次数（待排序序列长度 - 1），内层循环控的? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?是相邻两个元素进行交换，注意交换条件（j < arr.length - 1 -i）。
? ? ? ? ? ? ? ? ? ?（2）在一轮循环结束后，如果flag被置为true，则说明已为有序序列，不? ? ? ? ? ? ? ? ? ? ? ? ? ? 用再进行接下来的循环了。
二、快速排序:(对冒泡排序的一种改进)（平均时间复杂度：O(nlogn)）
? ? ? ? 1、基本思想：在待排序序列中选择一个基准元素，通过一趟排序后，将该序列分割成两个独立的部分，左边部分的元素都比该基准小，右边部分都比该基准大，然后在分别对这两部分进行递归处理，已次达到目的。
? ? ? ? 2、快速排序法示意图：
????????
? ? ? ? ?3、代码如下：
????????
public static void quickSort(int[] arr,int start,int end){
if(start >= end){//递归结束标志
return;
}
//把数组中的第0个数字作为标准数
int stard = arr[start];
int low = start;
int high = end;
while (low < high) {
while (low < high && stard <= arr[high]){
high --;
}//在右边找出一个比stard小的数
arr[low] = arr[high];//找到之后进行覆盖下标为low的数
while (low < high && stard >= arr[low]){
low ++;
}//在左边找出一个比stard大的数
arr[high] = arr[low];//找到之后进行覆盖下标为high的数
}
//把标准数赋给下标为low或high的数（此时low=high）
arr[low] = stard;
//进行递归，处理两边的数字
quickSort(arr,start,low);
quickSort(arr,low+1,end);
}? ? ? ? 注意：（1）任何递归都得注意结束标志，必然会陷入死循环。
? ? ? ? ? ? ? ? ? ?（2）在该算法中，选择了第0个数字作为标准数，所以当在右边找出了一? ????????????????????????????个比基准小的数时，可以直接赋值给左边下标为low的数（当然不? ?????????????????????????????同算法在细节上可能不一样，总体思想不变）。
三、归并排序：（平均时间复杂度：O(nlogn)）
? ? ? ? 1、基本思想：是利用归并的思想实现的排序算法，该算法采用经典的分治策略（分：将问题分成一些小的问题然后递归求解，治：将分阶段得到的各答案修补在一起。即为分而治之）。
? ? ? ? 2、归并排序图解：
? ? ? ? 分治总体图解：
????????
? ? ? ? ?治阶段的合并图解：
????????
? ? ? ? ?3、代码如下：
????????
//分+合的方法
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);
}
}
//合并的方法
/**
*
* @param arr 排序的原始数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 做中转的数组
*/
public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
int i = left;//左边有序序列的初始索引
int j =mid + 1;//右边有序序列的初始索引
int t = 0;//指向temp数组的当前索引
//1、把两个有序序列按照规则填充到temp数组中，直到一方已经处理完毕
while (i <= mid && j <= right) {
if(arr[i] <= arr[j]){
temp[t] = arr[i];
t++;
i++;
}else{
temp[t] = arr[j];
t++;
j++;
}
}
//2、把有剩余数据的有序序列直接填充到temp数组中
while (i <= mid){
temp[t] = arr[i];
t++;
i++;
}
while (j <= right){
temp[t] = arr[j];
t++;
j++;
}
//3、将temp数组的元素拷贝到arr（并不是拷贝所有）
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}? ? ? ? 解释：在margeSort()方法中，当向右递归进行分解完了后此时的待排序列为如图：
，可以看出为8个小的有序序列，然后再从此时对小的有序序列进行合并，直到回溯完，也就已经排好了序。
四、基数排序：（平均时间复杂度：O(n^k)）
? ? ? ? 1、介绍：基数排序是桶排序的扩展，它是将整数按位数进行切割，按照得到的位数，把相应的元素分配至某些桶中，以达到排序的目的。基数排序法是属于效率高的稳定性（对于相同的元素，排序前后的相对顺序不变）的排序法。
? ? ? ? 2、主要思想：将所有待比较数值统一为同样的数位长度，数位短的数前面补0。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序后，数列就已经排好了序。
? ? ? ? 3、基数排序的图文说明：（该序列的最高位数为百位，所以进行三次排序）
?
? ? ? ? ?4、代码如下：
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];
}
}
//2、得到最大数是几位数
int maxLength = (max + "").length();
//定义一个二维数组，表示10个桶，每个桶就是一个一维数组
//1、二维数组包含10个一维数组
//2、为了防止在放数据的时候，数据溢出，一维数组的长度为arr.length
//3、很明显基数排序就是空间换时间的经典算法
int[][] bucket = new int[10][arr.length];
//为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶每次放入的数据个数
int[] bucketElementCounts = new int[10];
//bucketElementCounts[0],记录的是bucket[0]桶放入的个数
for(int i = 0, n = 1; i < maxLength; i++,n *= 10){
//针对每一轮，每个元素对应的位数进行排序（第一次是个位，第二次是十位。。。）
for(int j = 0; j < arr.length; j++){
//取出每个元素对应位的值，放入到对应桶中
int digtiofElement = arr[j] / n % 10;
bucket[digtiofElement][bucketElementCounts[digtiofElement]] = arr[j];
bucketElementCounts[digtiofElement]++;
//比如53，表示放到bucket[3][bucketElementCounts[3]]中，bucketElementCounts[3]一开始为0，每放一个数就进行++
}
//按照这个桶的顺序，（一维数组的下标取出数据，放入原来数组）
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[index] = bucket[k][l];
index++;
}
}
//进行每一轮处理时，都需要将每个桶计数的数组置0
bucketElementCounts[k] = 0;
}
}
}