排序思路：将待排序数组分为有序区间和无序区间，每次从无序区间选择一个元素添加到有序区间指定位置，直至整个数组有序；
时间复杂度：O（n^2）
稳定性：不稳定
代码：
public static void selectionSort(int[] arr){
//优化
if (arr==null || arr.length<2){
//只有一个元素或者没有元素 直接返回
return;
}
for (int i=0;i
//min对应无序最小值的索引
int min=i;
for (int j=i+1;j
//更新最小元素的索引
min =arr[j]
int temp= arr[i];
arr[i] =arr[j];
arr[j]=temp;
}
优化版本：双向选择排序
public static void selectionSortOP(int[] arr){
//定义两个变量分别从数组的头尾双向选择
int low=0;
int high=arr.length-1;
while (low
int min=low; //最小值对应的索引
int max=low; //最大值对应的索引
for (int i = low+1; i <=high ; i++) {
if (arr[i]
min=i;
}
if (arr[i]>arr[max]){
max =i;
}
}
//经过以上循环，min对应区间的最小值，max对应区间的最大值
//交换min和low位置
swap(arr,min,low);
if (max ==low){
//最大值已经被交换到min这个位置
max =min;
}
swap(arr,max,high);
low+=1;
high-=1;
}
}
//交换元素
private static void swap(int[] arr, int i, int j) {
int temp= arr[i];
arr[i] =arr[j];
arr[j]=temp;
}
2.冒泡排序
排序思路：遍历原数组，依次比较前后元素的大小，如果后一元素比前一元素小，则交换它们位置，否则继续向后遍历，直至整个数组有序；
时间复杂度：O（n^2）
稳定性：稳定
代码：
public static void bubbleSortPlus(int[] arr){
int temp;
for (int i = 0; i < arr.length ; i++) {
//布尔值标记当前数组是否已经达到有序状态
boolean flag =true;
for (int j = 0; j < arr.length-1-i ; j++) {
if (arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
//本次发生了交换
flag =false;
}
}
//根据标记值判断数组是否有序，如果有序则退出，无序继续循环
if (flag){
break;
}
}
}
3.直接插入排序
排序思路：每次从无序区间选择一个数插入到合适的位置，插入过程类似于扑克牌的码牌过程，插入排序虽然是O（N^2）的排序算法，但是在近乎有序的数据集上，插入排序的性能甚至优于NlogN的排序算法，所以，插入排序也作为其他高阶排序算法的优化手段；
时间复杂度：O（N^2）
稳定性：稳定
代码：
public static void bubbleSort(int[] arr){
if (arr ==null || arr.length<2){
return;
}
for (int i = arr.length-1; i >0 ; i--) {
for (int j = 0; j < i ; j++) {
if (arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
private static void swap(int[] arr, int j, int i) {
int temp=arr[i];
arr[i] =arr[j];
arr[j]=temp;
}
优化：引入标记位
public static void insertionSort(int[] arr){
for (int i = 1; i < arr.length ; i++) {
//从待排序区间不断向前看，找到合适的插入位置
for (int j = i; j >0 ; j--) {
if (arr[j]>=arr[j-1]){
//表明arr[j]已经有序，相等也不交换，保证稳定性
break;
}else {
swap(arr,j,j-1);
}
}
//以上代码等同于
public static void insertSortBS(int[] arr){
//有序区间：[0,i) 无序区间：[i,n]
for(int i=1;i< arr.length;i++){
int val =arr[i];
int left =0;
int right =i;
while (left
int mid =left+((right-left)>>1); //相当于（left+right）/2
if (val < arr[mid]) {
right=mid;
}else {
left=mid+1;
}
}
//搬移[left,i]的元素
for (int j=i;j>left;j--){
arr[j]=arr[j-1];
}
arr[left] =val;
}
}
4.堆排序
排序思路：任意数组都可视为一颗完全二叉树，将数组调整为一个最大堆，然后再将元素下沉，重复以上操作，数字就调整为有序；
时间复杂度：O（nlogN）
稳定性：稳定
代码：
public static void heapSort(int[] arr){
//1、先将数组调整为最大堆
//从最后一个非叶子节点来时进行元素下沉
for (int i=(arr.length-1-1)/2; i>=0;i--){
//下沉终止位置就是arr.length
siftDown(arr,i,arr.length);
}
//此时，数组已经被调整为最大堆，遍历数组
for (int i = arr.length-1; i >0 ; i--) {
//arr[0]:堆顶元素，就是最大值
swap(arr,0,i);
siftDown(arr,0,i);
}
}
private static void siftDown(int[] arr, int i, int length) {
//只有当前节点存在左右孩子时元素才可以下沉
while (2*i+1
int j =(i<<1)+1;
if (j+1 arr[j]){
//此时，右子树为最大值
j=j+1;
}
//当前元素已经大于左右子树的最大值
if (arr[i] > arr[j]){
//下沉结束
break;
}else {
//交换俩元素的位置
swap(arr,i,j);
//继续向后遍历，下沉元素
i=j;
}
}
}
//交换元素
private static void swap(int[] arr, int i, int j) {
int temp= arr[i];
arr[i] =arr[j];
arr[j]=temp;
}
希尔排序、快速排序、归并排序，请看下篇博客：【算法】七大排序详解(下篇)
创作不易，麻烦亲点赞收藏啦
