声明：基于比较的排序算法基本原理及实现为面试常考知识点，务必重视！
通过本篇文章可以掌握：
- 掌握七大基于比较的排序算法基本原理及实现
- 掌握排序算法的性能分析
- 掌握 java 中的常用排序方法
文章目录：
1、排序
1.1、排序的概念
1.2、稳定性
对于稳定性的定义：
图解上述说法：
2、七种基于比较的排序
七种排序总览表：
2.1、 直接插入排序
①、整体思路及实现过程
②、直接插入排序代码：
public static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
int j = i - 1;
int tmp = arr[i];
for(; j >= 0; j--){
if(arr[j] > tmp){
arr[j + 1]= arr[j];
}else{
break;
}
}
arr[j+1] = tmp;
}
}
③、直接插入排序结果：
④、性能分析
⑤、使用场景：
2.2、 希尔排序
①、整体思路及实现过程
②、希尔排序代码：
private static void shell(int gap,int[] arr){
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
for (; j >= 0; j = j - gap) {
if(arr[j] > tmp){
arr[j+gap] = arr[j];
}else{
break;
}
}
arr[j+gap] = tmp;
}
}
public static void shellSort(int[] arr){
int gap = arr.length/2;
while(gap > 1){
shell(gap,arr);
gap = gap / 2;
}
shell(1,arr);
}
③、希尔排序结果：
④、性能分析
2.3、 选择排序
①、整体思路及实现过程
②、选择排序代码：
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
if(arr[i] > arr[j]){
swap(i,j,arr);
}
}
}
}
//优化
public static void selectSort1(int[] arr){
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i+1; j < arr.length; j++) {
if(arr[minIndex] > arr[j]){
minIndex = j;
}
}
swap(i,minIndex,arr);
}
}
③、性能分析
2.4、 堆排序
①、整体思路及实现过程
②、堆排序代码：
private static void shiftDown(int parent, int len,int[] arr){
int child = 2*parent + 1;
while(child < len){
if(child + 1 < len && arr[child] < arr[child+1]){
child = child + 1;
}
if(arr[child] > arr[parent]){
swap(parent,child,arr);
parent = child;
child = 2 * parent + 1;
}else{
break;
}
}
}
public static void heapSort(int[] arr){
for (int parent = (arr.length - 1 - 1) / 2; parent >= 0 ; parent--) {
shiftDown(parent,arr.length,arr);
}
int end = arr.length - 1;
while(end != 0){
swap(0,end,arr);
shiftDown(0,end,arr);
end--;
}
}
③、性能分析
2.5、 冒泡排序
①、冒泡排序过于简单直接展示代码：
public static void bubbleSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
boolean flg = false;
for (int j = 0; j < arr.length - i - 1; j++) {
if(arr[j+1] < arr[j]){
swap(j+1,j,arr);
}
flg = true;
}
if(!flg){
break;
}
}
}
②、性能分析：
2.6、 快速排序
①、整体思路及实现过程
基准选取方法：选取边上法
基准选取法：三数取中法
这里只展示三数取中的快速排序代码，取边法去掉三数寻找中间值和交换的步骤即可
private static int partion(int[] arr,int start,int end){
int tmp = arr[start];
while(start < end){
while(start < end && arr[end] > tmp){
end--;
}
arr[start] = arr[end];
while(start < end && arr[start] < tmp){
start++;
}
arr[end] = arr[start];
}
arr[end] = tmp;
return end;
}
private static int midValueSearch(int[] arr,int start,int end){
int mid = start + ((end - start) >>> 1);
if(arr[start] < arr[end]){
if(arr[mid] < arr[start]){
return start;
}else if(arr[mid] > arr[end]){
return end;
}else{
return mid;
}
}else{
if(arr[mid] < arr[end]){
return end;
}else if(arr[mid] > arr[start]){
return start;
}else{
return mid;
}
}
}
private static void quick(int[] arr,int left,int right){
if(left >= right){
return;
}
int midValue = midValueSearch(arr,left,right);
swap(left,midValue,arr);
int pivot = partion(arr,left,right);
quick(arr,left,pivot-1);
quick(arr,pivot+1,right);
}
public static void quickSort(int[] arr){
quick(arr,0,arr.length-1);
}
上面的快速排序是使用递归方法实现的，那么非递归可以怎样去实现快速排序呢？
快速排序的非递归算法：
public static void quickSort1(int[] arr){
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = arr.length - 1;
int pivot = partion(arr,left,right);
if(pivot > left + 1){
stack.push(left);
stack.push(pivot - 1);
}
if(pivot < right - 1){
stack.push(pivot + 1);
stack.push(right);
}
while(!stack.isEmpty()){
right = stack.pop();
left = stack.pop();
pivot = partion(arr,left,right);
if(pivot > left + 1){
stack.push(left);
stack.push(pivot - 1);
}
if(pivot < right - 1){
stack.push(pivot + 1);
stack.push(right);
}
}
}
②、性能分析：
2.7、归并排序
①、整体思路及实现过程
private static void mergeSortInter(int[] arr,int low,int high){
if(low >= high){
return;
}
int mid = low + ((high - low) >>> 1);
mergeSortInter(arr,low,mid);
mergeSortInter(arr,mid + 1,high);
merge(arr,low,mid,high);
}
private static void merge(int[] arr,int low,int mid,int high){
int[] tmp = new int[high - low + 1];
int s1 = low;
int e1 = mid;
int s2 = mid + 1;
int e2 = high;
int i = 0;
while(s1 <= e1 && s2 <= e2){
if(arr[s1] <= arr[s2]){
tmp[i++] = arr[s1++];
}else{
tmp[i++] = arr[s2++];
}
}
while(s1 <= e1){
tmp[i++] = arr[s1++];
}
while(s2 <= e2){
tmp[i++] = arr[s2++];
}
for (int j = 0; j < i; j++) {
arr[j+low] = tmp[j];
}
}
public static void mergeSort(int[] arr){
mergeSortInter(arr,0,arr.length-1);
}
上面的代码是递归实现的，那么非递归又是怎样实现归并排序的呢？
public static void mergeSort1(int[] arr){
int nums = 1;
while(nums < arr.length){
for (int i = 0; i < arr.length; i+=nums*2) {
int left = i;
int mid = left + nums - 1;
if(mid >= arr.length){
mid = arr.length - 1;
}
int right = mid + nums;
if(right >= arr.length){
right = arr.length - 1;
}
merge(arr,left,mid,right);
}
nums = nums * 2;
}
}
②、性能分析：
3、海量数据的排序问题
4、其他非基于比较的排序
这三个排序了解即可，附上链接，依照自身情况学习，博主只挑选了计数排序进行编写
4.1、基数排序
4.2、计数排序
public static void countingSort(int[] arr){
int minVal = arr[0];
int maxVal = arr[0];
for (int j : arr) {
if (j > maxVal) {
maxVal = j;
}
if (j < minVal) {
minVal = j;
}
}
int[] count = new int[maxVal - minVal + 1];
for (int j : arr) {
count[j-minVal]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while(count[i] > 0){
arr[index] = i + minVal;
index++;
count[i]--;
}
}
}