总结几种简单的排序
插入排序：
这个排序属于稳定排序（两个相等的数据在排序前和排序后的相对位置没有改变），它的时间复杂度平均为 O（n2）。排序的过程可以大体概述为（按升序）：第n项数值和前（n-1）项的所有数字比较，如果第n项的数值比这所有n-1项的数字都大，则位置不变，如果发现第n项比前n-1项数字小，则这两个数据互换位置，换完之后再和当前位置之前的数字进行比较，依次类推。借一副比较好的图和大家说明：
图片来源：https://blog.****.net/qq_42857603/article/details/81605124
实现代码：
import java.util.Arrays;
public class charu {
public static void main(String[] args) {
int tmp,j;
int[] array={1,4,7,23,5,2,6,8};
for(int i=0;i<array.length;i++){//第i位数字
tmp=array[i];
for( j=i-1;j>0;j--){//与第i位数字之前的数字进行逐个比较
if(tmp>array[j]){
break;
}else{
array[j+1]=array[j];
}
}
//因为在内循环中j--已经到了j位的前面一位，所以之前的j位已经为空，j+1是
//到了之前的j为
array[j+1]=tmp;
}
System.out.println(Arrays.toString(array));
}
}
选择排序：
这种排序的基本思路是（以升序打比方）:遍历整个数组，找出最小的值放到最左边第一位，剩下的数组中的数字重复上一步，即找到这些数字中最小的一位，放到第二为，以此类推。此种排序方式的时间复杂度是O（n2）
实现代码：
import java.util.Arrays;
public class xuanze {
public static void main(String[] args) {
int i,j,mindex;
int [] array={1,5,3,6,8,3,5,7};
for(i=0;i<array.length-1;i++){
mindex=i;
for(j=i+1;j<array.length;j++){
//循环找出i+1到数组末尾中的最小值
if(array[mindex]<array[j]){
mindex=j;
}
}
if(i!=mindex){
int tmp=array[i];
array[i]=array[mindex];
array[mindex]=tmp;
}
}
System.out.println(Arrays.toString(array));
}
}
冒泡排序：
这种排序的基本思路是，相邻的两位进行比较，如果右边一位大于左边一位，则进行互换，反之则不换位置。这种排序方式的时间复杂度为O（n2）。
实现代码：
public class maopao {
public static void main(String[] args) {
int[] array={1,6,3,7,4,9,4,6};
for(int i=0;i<array.length;i++){
for(int j=0;j<array.length-i-1;j++){
if(array[j]>array[j+1]){
int tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
}
}
}
System.out.println(Arrays.toString(array));
}
}
快速排序：
相比于冒泡排序，快速排序的交换式跳跃式的。每次排序时候都要设置一个基准点，将小于等于基准点的数全部放在基准点的左边，将大于等于基准点的数全部放在基准点的右边，这样在每次交换的时候就不会想冒泡排序一样每次都只能在相邻的数之间进行交换，交换的距离就大的多了。第一次排序完毕以后，就分成两个部分，这两个部分进行同样的排序操作，以此类推，直到所有的数字都排完，这样就会全局排序了。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。
实现代码：
public class QuickSort {
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i<j) {
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
public static void main(String[] args){
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
堆排序：
堆排序就比较棘手了，因为它涉及到二叉树的知识，如果二叉树知识比较薄弱的兄弟们建议先看一下相关的知识。堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
· 步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
· 步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
再简单总结下堆排序的基本思路：
· a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
· b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
· c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
实现代码：
import java.util.Arrays;
public class dui {
public static void main(String[] args) {
int [] a ={1,3,6,2,4,6,2,4,1};
heapSort(a);
System.out.println(Arrays.toString(a));
}
static void heapSort(int []a){
int len=a.length;
buildMaxHeap(a, len);
int tm=a[0];
a[0]=a[len-1];
a[len-1]=tm;
//建堆之后还要进行len-2次排序
for(int i=1;i<len-1;i++){
maxHeapfy(a, 0, len-i);
int ab=a[0];
a[0]=a[len-1-i];
a[len-1-i]=ab;
}
}
static int parent(int i){
return (i-1)/2;
}
static int left(int i){
return 2*i+1;
}
static int right(int i){
return 2*i+2;
}
/**
* 保持大根堆性质
*/
static void maxHeapfy(int []a,int i,int heapSize){
int left=left(i);
int right=right(i);
int largest=i;
//如果当前值小于左孩子，则换坐标
if(left<heapSize&&a[largest]<a[left]){
largest=left;
}
if(right<heapSize&&a[largest]<a[right]){
largest=right;
}
//将最大值交给父节点
if(largest!=i){
int tmp=a[largest];
a[largest]=a[i];
a[i]=tmp;
maxHeapfy(a,largest,heapSize);
}
}
//构建大根堆
static void buildMaxHeap(int[]a,int heapSize){
for(int i=(heapSize-2)/2;i>=0;i--){
maxHeapfy(a, i, heapSize);
}
}
}