数据结构学习的排序部分成果分享：
此博客共分享七种排序：选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、基数排序
1.选择排序：
代码部分（java）：
public static void selectSort(int[] array){
if(array==null || array.length<2){
return;
}
for(int i =0 ; i< array.length-1 ; i++){
int minIndex = i;
for(int j = i+1; j
解读：定义一个数组：{2，5，3，1，4}
一次选择排序在5个数中选出最小的一个数，在该数组中即为1，此时下标minIndex即为1的下标，内部循环的最后让最小的1与第一个数交换
二次排序在除1以外的四个数中进行，过程如上，此时下标minIndex即为2的下标，同样在内部循环的最后让2与数组第二个数字交换
.........
依次重复该过程找出剩余数字中的最小值使其处于余下数字的第一位即可完成整体排序
时间复杂度：O(N^2) 空间复杂度：O（1）
稳定性：不具有稳定性
2.冒泡排序
代码部分：
public static void bubbleSort(int[] array) {
if (array == null || array.length <2) {
return;
}
for (int i = array.length-1; i >0; i--) {
for ( int j = 0; j < i; j++){
if (array[j] > array[j+1]) {
swap01(array, j, j+1);
}
}
}
}
解读：定义一个数组{2，5，3，1，4}
整体思想就是相邻两个数比较，每次让最大的数移至数组末尾然后i--，即每次选出余下数字的最大值
时间复杂度：O（N^2） 空间复杂度：O（1）
稳定性：具有稳定性
3.插入排序
代码部分：
public static void insertSort(int[] array) {
if (array==null||array.length<2){
return;
}
for (int i = 1; i < array.length; i++) {
for (int j = i-1; j >=0&&array[j]>array[j+1] ; j--) {
swap01(array,j,j+1);
}
}
}
解读：定义一个数组{2，5，6，1，2，3，9}
核心思想：从头依次将下标为i的数与其之前的数进行比较，然后插入到其指定的位置
时间复杂度:O(N^2) 空间复杂度:O(1)
稳定性:具有稳定性
4.归并排序
代码部分
public static void process(int[] arr,int left,int right){
if (left==right){
return;
}
int mid = left + ((right-left)>>1);
process(arr,left,mid);
process(arr,mid+1,right);
merge(arr,left,mid,right);
}
public static void mergeSort(int[] arr){
if (arr == null|| arr.length <2){
return;
}
process(arr,0,arr.length-1);
}
public static void merge(int[] arr,int left,int mid,int right){
int[] help = new int[right-left+1];
int i = 0;
int num1 = left;
int num2 = mid+1;
while(num1<=mid&&num2<=right){
help[i++] = arr[num1] <=arr[num2] ? arr[num1++] : arr[num2++];
}
while(num1<=mid){
help[i++] = arr[num1++];
}
while (num2<=right){
help[i++] = arr[num2++];
}
for (int j = 0; j < help.length; j++) {
arr[left+j] = help[j];
}
}
解读：定义一个数组{5,2,6,4,3,8}
核心思想就是分治，即实现部分有序，然后实现整体有序
时间复杂度：O（NlogN） 空间复杂度:O（N）
稳定性：具有稳定性
5.快速排序
代码部分:
public static void quickSort(int[] arr){
if (arr==null || arr.length<2){
return;
}
quickSort(arr,0,arr.length-1);
}
public static void quickSort(int[] arr,int left,int right){
if (left
解读:定义一个数组:{2,5,6,1,3,4}
核心思想是随机取出数组中的一个数与数组最后一个数进行交换，然后将数组分成小于该数、等于该数、大于该数三部分，
然后用这样的思想使小于部分和大于部分分别有序，最后使整体有序.
时间复杂度:O(NlogN) 空间复杂度:O(logN)
稳定性：不具有稳定性
6.堆排序
代码部分：
public static void heapSort(int[] arr){
if (arr==null||arr.length<2){
return;
}
for (int i = 0; i < arr.length; i++) { //O(N)
heapInsert(arr,i); //O(logN)
}
int heapSize = arr.length;
swap(arr,0,--heapSize);
while (heapSize>0){ //O(N)
heapify(arr,0,heapSize); //O(logN)
swap(arr,0,--heapSize); //O(1)
}
}
public static void heapInsert(int[] arr, int index){
while (arr[index] > arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index = (index-1)/2;
}
}
public static void heapify(int[] arr,int index,int heapSize){
int left = index*2+1;
while (left arr[left] ? left+1:left;
largest = arr[largest] > arr[index] ? largest:index;
if (largest==index){
break;
}
swap(arr,largest,index);
index = largest;
left = index*2+1;
}
}
解读：定义一个数组{2，5，6，7，1，4，3}
整体思路：先构造一个大根堆
然后将最后一个数与第一个数（最大的数）交换，随之将其与自己的子节点对比，如果小于子节点中的较大值则与其交换，重复这个过程则可以实现依次挑出剩余最大值，利用--heapSize将剩余最大值搁置在堆底，即完成了从后向前的排序。
时间复杂度：O（NlogN） 空间复杂度：O（1）
稳定性：不具有稳定性
7.基数排序
代码部分：
public static void radixSort(int[] arr){
if (arr==null || arr.length<2){
return;
}
radixSort(arr,0,arr.length-1,maxbits(arr));
}
private static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max,arr[i]);
}
int res = 0;
while (max!=0){
res++;
max/=10;
}
return res;
}
public static void radixSort(int[] arr,int left,int right,int digit){
final int radix = 10;
int i = 0,j = 0;
int[] bucket = new int[right-left+1];
for (int d = 1;d<=digit;d++){
int[] count = new int[radix];
for (i = left;i<=right;i++){
j = getDigit(arr[i],d);
count[j]++;
}
for (i = 1;i=left;i--){ //重点
j = getDigit(arr[i],d);
bucket[count[j]-1] = arr[i]; //分别按个,十,百位上数字大小排序
count[j]--;
}
for (i = left,j = 0;i<=right;i++,j++){
arr[i] = bucket[j];
}
}
}
public static int getDigit(int x,int d){
return ((x/((int)Math.pow(10,d-1)))%10);
}
解读：定义一个数组{123，45，456，345，23，6，567}
整体思路：取出每个数字的个、十、百位进行排序
先排序各数的个位即123，23，45，345，456，6，567
再排序各数的十位即6，23，123，45，456，567
最后排序各数的百位即，6，23，45，123，456，567
