排序
一、排序种类
1.交换排序
（1）冒泡排序
（2）快速排序
2.插入排序
（1）直接插入排序
（2）希尔排序
3.选择排序
（1）简单选择排序
（2）堆排序（与二叉树有关，暂时先不实现）
4.归并排序
5.基数排序
二、排序实现
1.冒泡排序
思想：（1）对于每两个相邻的元素进行交换，如果是从小到大排序，则每次将最大的交换到最后一位，需要执行（array.length-1）次，每次需要交换（array.length-i-1）次，其中i属于[0,array.length-1)；如果是从大到小排序，则是将最小的交换到后面。
（2）若是某一次不需要交换了，则说明不需要执行后面的交换次，可以直接跳出，实现对冒泡排序的优化。
代码如下（示例）：
// 冒泡排序
public void BubbleSort(int[] arr){
boolean flag = true;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if(arr[j] > arr[j+1]){ //从小到大排序
flag = false;
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.println("第"+(i+1)+"趟排序后的数组："+ Arrays.toString(arr));
// 优化 -- 如果已经有序则直接跳出
if (flag){
break;
}
}
}
2.选择排序
思路：如果是从小到大排序，则将array[i]与min（arr[j]）(j = [i+1,array.length-1])进行交换，即每一次找出（i+1）到（array.length）的最小值，与array[i]交换。
代码如下（示例）：
// 选择排序
public void selectSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
int min = arr[i];
int minIndex = i;
boolean flag = false;
for (int j = i+1; j < arr.length; j++) {
if(min > arr[j]){
flag = true;
min = arr[j];
minIndex = j;
}
}
if(flag){
int temp = arr[i];
arr[i] = min;
arr[minIndex] = temp;
}
System.out.println("第"+(i+1)+"趟排序后的数组："+ Arrays.toString(arr));
}
}
3.插入排序
思想：（1）首先将数组看成一个有序表和一个无序表，有序表中暂存第一个数，其他的都存在无序表中；
（2）依次取出无序表中的每一个数与有序表中的数进行比较，将其插入到一个适合的位置。
代码如下（示例）：
// 插入排序
public void insertSort(int[] arr){
// for (int i = 0; i < arr.length - 1; i++) {
// for (int j = i+1; j < arr.length; j++) {
// if(arr[i] > arr[j]){ //从小到大排序
// int temp = arr[i];
// arr[i] = arr[j];
// arr[j] = temp;
// }
// }
// System.out.println("第"+(i+1)+"趟排序后的数组："+ Arrays.toString(arr));
// }
for (int i = 1; i < arr.length; i++) {
int insertVal = arr[i];
int insertIndex = i - 1;
while (insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex +1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = insertVal;
System.out.println("第"+i+"趟排序后的数组："+ Arrays.toString(arr));
}
}
4.希尔排序
思想：gap = arrar.length/2
（1）每一次将数组分成gap = gap/2组；
（2）每一组的i=gap与j=i-gap比较,如果array[i]比较大，则交换，就这样一直进行到i=array.length。
（3）直到gap不能再分的时候退出。
代码如下（示例）：
//希尔排序（交换法)
public void donaldShell1(int[] arr){
int count = 0;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
count++;
for (int i = gap; i < arr.length ; i++) {
for (int j = i - gap; j >= 0; j -= gap) {
if(arr[j] > arr[j + gap]){
int temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
System.out.println("第"+count+"趟排序后的数组："+ Arrays.toString(arr));
}
}
//希尔排序（移位法）
public void donaldShell2(int[] arr){
int count = 0;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
count++;
for (int i = gap; i < arr.length ; i++) {
int j = i;
int temp = arr[j];
if(arr[j] < arr[j - gap]){
while (j - gap >= 0 && temp < arr[j - gap]){
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
System.out.println("第"+count+"趟排序后的数组："+ Arrays.toString(arr));
}
}
5.快速排序
思想：（1）确定一个数组元素，将小于它的放到左边，大于他的放到右边；
（2）再根据递归的思想再对左边和右边进行快速排序。
代码如下（示例）：
public void QuickSort(int[] arr, int left, int right){
int l = left;
int r = right;
int middle = arr[(left + right) / 2]; //中间值
while (l < r){
// 寻找数组左边大于中间数的元素
while (arr[l] < middle){
l += 1;
}
// 寻找数组右边大于中间数的元素
while (arr[r] > middle){
r -= 1;
}
// 如果左边的数都小于中间结点，右边的数都大于中间结点，则退出
if( l >= r){
break;
}
// 交换
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
// 没有的话会出现栈溢出
if(l == r){
l += 1;
r -= 1;
}
// 对左边进行快速排序
if(left < r){
QuickSort(arr,left,l);
}
// 对右边进行快速排序
if(right > l){
QuickSort(arr,l,right);
}
}
6.归并排序
思想：（1）合并过程：将数组的两个有序子序列合并到一个临时数组中；然后将其中一个子序列剩余的元素合并到临时数组中；将临时数组的值赋给原数组。
（2）分解过程：将其左递归分解；再进行右递归分解；然后进行合并。
代码如下（示例）：
//归并排序
public 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 void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid + 1;
int t = 0;
// 1、将两个子序列合并到一个临时数组中
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
i += 1;
t += 1;
} else {
temp[t] = arr[j];
j += 1;
t += 1;
}
}
// 2、将两个子序列中剩余的元素直接复制到temp中
while (i <= mid) {
temp[t] = arr[i];
i += 1;
t += 1;
}
while (j <= right) {
temp[t] = arr[j];
j += 1;
t += 1;
}
// 3、将temp的数复制给arr
t = 0;
int tempLeft = left;
System.out.println("tempLeft=" + tempLeft + ",right=" + right);
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
7.基数排序
思想：（1）创建一个（0-9）的二维数组作为桶，进行存放每一轮比较的数据；
（2）每一轮对数组中的每个数的（个/十/百…(取决于数组中的最大数位数的个数））进行排序，按照大小放入二维数组中，其中可以利用一个一维数组记录一下个数；
（3）每一轮都将其从桶中按桶的顺序取出得到新的序列，其中数组的最大数有几位数总共就需要执行几次，最后一次就可以得到最终结果。
代码如下（示例）：
//基数排序
public void radixSort(int[] arr) {
int[][] bucket = new int[10][arr.length];
int[] bucketElementCounts = new int[10]; // 记录每个桶中元素的个数
// 找出数组最大数的位数
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if(max < arr[i]){
max = arr[i];
}
}
int maxLength = (max + "").length();
for (int l = 0 , n = 1; l < maxLength; l++, n *= 10) {
// 每一轮，将每个元素的个位数取出来，放入桶中
for (int i = 0; i < arr.length; i++) {
int index = arr[i] / n % 10;
bucket[index][bucketElementCounts[index]] = arr[i];
bucketElementCounts[index]++;
}
// 按照桶的顺序将数据取出放入原来的数组中
int i = 0;
while (i < arr.length) {
for (int j = 0; j < 10; j++) {
if(bucketElementCounts[j] != 0){
for (int k = 0; k < bucketElementCounts[j]; k++) {
arr[i++] = bucket[j][k];
}
}
// 第一轮处理后，需要将每个bucketElementCounts[k] = 0;
bucketElementCounts[j] = 0;
}
}
System.out.println("第" + (l+1) + "趟排序后的数组：" + Arrays.toString(arr));
}
}
总结
冒泡排序（稳定）、选择排序（不稳定）、插入排序（稳定）的平均时间复杂度是：O(n^2)；
希尔排序（不稳定）、归并排序（稳定）、快速排序（不稳定）的平均时间复杂度是：O(n*(log n))；
基数排序（稳定）的平均时间复杂度是：O(n*k)。