1、冒泡排序 Bubble Sort
基本思路：两两元素进行比较，前一个比后一个大就交换，直到将最大的元素交换到末尾位置。这是第一趟。一共进行n-1趟这样的交换将可以把所有的元素排好。就像水里面的泡泡一样，会一直上升，且上升的过程还会慢慢增大
冒泡排序每次都唔确定一个元素的最终位置，代码如下：
public static void Bubble(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length-1;j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}2、快速排序 Quick Sort
基本思想：就是分治法，每次我们确定一个基准值的最终位置，然后基准值左边都是小于基准值的，而右边都是大于基准值的，以此达到局部有序，然后递归，最终得到有序数组
1、选择基准值：确定一个基准值，理论上可以任意选用基准值，但是为了
方便起见，最好选用最左边或者最右边的元素为基准值，选用中间的会给自己添麻烦
2、分区：在这里，我们选用最左边的元素为基准值，然后定义两个指针分别指向
待排序数组的两端（left指针、right指针，这两个指针会分别向中间遍历），left指针先 移动，当left指针的值小于基准值时停下，然后right指针再走，遇到大于基准值的数就停 下来，交换left和right指针对应位置的值。
重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。
3、递归：对分区后的两个子数组（基准值左边的子数组和右边的子数组）分别重 复以上步骤，直到子数组的大小为1或0时终止递归。
代码如下：
public static void Quick(int[] arr,int left,int right){
//l和r是边界指针
int l=left;
int r = right;
//选定左边为基准值
int key = left;
if(left>=right){
return;
}
while(left<right){
//左指针移动，遇到小于基准值时，进行交换
if(arr[key]>arr[left+1]){
int temp = arr[key];
arr[key] = arr[left+1];
arr[left+1] = temp;
key = left+1;
left++;
}else{
//右指针移动
int temp=arr[left+1];
arr[left+1]=arr[right];
arr[right] = temp;
right--;
}
}
//对左半部分重复上述步骤
if(left-l>1) {
Quick(arr, l, left-1);
}
//对右半部分重复上述步骤
if(r-right+1>1) {
Quick(arr, right+1, r);
}
}3、简单插入排序 Insert Sort
基本思想：默认左边第一个元素是有序子元素，然后从第二个开始，依次向前比较，如果大于该元素，则交换位置，直到小于该元素位置，以此类推，直到数组有序
代码如下：
public void insertSort(int[] arr){
for(int i=1;i<arr.length;i++){
for(int j=i-1;j>=0;j--){
if(arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}4、希尔排序 Shell Sort
基本思想：利用了分组的思想
1.首先选择一个步长值gap，以步长值为间隔把数组分为gap个子数组gap=length/2
2.对每个子数组进行插入排序；
3.逐步减小步长 gap = gap/2,重复对数组进行1，2 步骤；
4.当步长值减为1时，相当于对数组进行一次直接插入排序。
public static void ShellSort(int[] arr) {
for(int group = arr.length/2;group>=1;group/=2) {
for(int i=group;i<arr.length;i++) {
for(int j = i-group;j>=0;j-=group) {
if(arr[j]>arr[j+group]) {
int temp = arr[j];
arr[j] = arr[j+group];
arr[j+group] = temp;
}
}
}
}
}5、简单选择排序 Search Sort
基本思想：首先将首元素定为基准，然后遍历，遇到比基准小的，先记录位置，标为新的最小值，遍历完成后，让最小值与基准交换 位置
每一次都能确定一个元素的最终位置
public static void SearchSort(int[] arr) {
for(int j = 0;j<arr.length;j++) {
int min=arr[j];
int minIndex=j; //记录最小值位置
for(int i = j+1;i<arr.length;i++) {
if(arr[i]<min) {
min = arr[i];
minIndex = i;
}
}
//位置交换
int temp = arr[j];
arr[j] = arr[minIndex];
arr[minIndex]= temp;
}
}6、堆排序 Heap Sort
基本思想：
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
在得到完全二叉树后，按顺序加上下标，我们可以发现：结点i的左子树节点表示为2i+1，右子树为2i+2，父节点为（i-1）/2
代码实现大根堆思想（定义一个parent游标、child游标）：
1、让parent从后往前移动，知道parent有孩子
2、让child指向左右孩子当中值最大的那个
3、让parent指向的值和child的值进行对比交换，
4、一旦完成交换，就让parent指向child指向的位置，child继续指向左右孩子当作最大的
重复执行3、4步，知道parent指向的值大于child的值或者child指空为止
代码实现堆排序思想：首先构建大根堆，然后让堆顶元素和堆底元素进行互换，然后堆底不在参与下一轮构建
public static void HeapSort(int[] arr) {
for(int p =arr.length;p>=0;p--) {
sort(arr, p,arr.length);
}
//堆顶元素与堆底元素互换，且堆底元素不在参与新一轮构建
for(int i=arr.length-1;i>0;i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
sort(arr, 0, i);
}
}
public static void sort(int[] arr,int parent,int length) {
//其实parent不是主动移动，他是被上述方法p带着动的
int child = 2*parent+1; //若有孩子，一定有左孩子
while(child <length) {
int rchild = child+1; //右孩子
if(rchild<length &&arr[child]<arr[rchild]) {
child = rchild;
}
//父子节点之间进行对比交换
if(arr[parent]<arr[child]) {
int temp = arr[parent];
arr[parent] = arr[child];
arr[child] = temp;
//parent指向孩子节点
parent = child;
child = 2*child+1;
}else {
break; //跳出循环
}
}
}7、归并排序 Merge Sort
基本思想：
首先应在数组中找出有序的序列，但数组是否有序编译器可不知道。
所以可以将数组划分，一分二，二分四......直到每个序列中只有一个数字。
一个数字总可以认为他是有序的吧。
最后将同时划分的序列合并。
public static void MergeSort(int[] arr,int left,int right,int mid){
//先进行拆分
if(left==right){
return;
}
//向左侧进行递归拆分
MergeSort(arr,left,mid,(left+mid)/2);
//向右侧进行递归拆分
MergeSort(arr,mid+1,right,(mid+1+right)/2);
//进行合并排序
sort(arr,left,right,mid);
}
public static void sort(int[] arr,int left,int right,int mid){
//定义临时数组
int[] temp=new int[arr.length];
//定义两个游标，分别指向已拆分数组的头部
int s1=left;
int s2=mid+1;
while(s1<=mid &&s2<=right){
if(arr[s1]>arr[s2]){
int temp = arr[s1];
}
}
}8、基数排序 Radix Sort
基本思想：从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
步骤：
1、首先准备10个桶（0~9）（显然，桶应该是二维的，大小是10×arr.length），取数组中每一个元素个位的值，分别装 入对应的桶中
2、找十位的数字，重复步骤一，在找出百位的数字，同样重复步骤一。最后arr数组就会按照升序排序结束。
public static void RadixSort(int[] arr){
//定义一个二维数组，模拟桶的实现
int bucket[][] = new int[10][arr.length];
//一个桶计数器，记录桶中有多少数据，在插入时使用
int[] bucketCount = new int[10];
//查找最大元素，确定循环轮数
int max=arr[0];
for(int i =0;i<arr.length;i++){
if(max<arr[i]){
max=arr[i];
}
}
//获取最大值位数
int maxLength = (max+"").length();
//控制排序的最大位数（个、十、百）
int n=1;
for(int i=0;i<maxLength;i++){
//往桶中装入数据,第一轮是个位，因为除的n=1
for(int j=0;j<arr.length;j++){
int element=arr[j]/n%10;
int count = bucketCount[element];
bucket[element][count] = arr[j];
bucketCount[element]++;
}
//将桶中数据取出
int a=0;
for(int i=0;i<bucketCount.length;i++){
if(bucketCount[i]!=0){ //说明桶中有数据
for(int k=0;k<bucketCount[i];k++){
arr[a]=bucket[i][k];
a++;
}
}
}
n*=10;
}
}
