插入排序：
-
直接插入排序
基本原理：对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余记录为无序序列，接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。
public class InsertSort {
public static int[] sort(int[] n){
if(n.length<=0){
return null;
}
//从第二个元素开始进行对比判断
for(int i=1;i<n.length;i++){
int temp=n[i];
int j=i;
if(n[j-1]>temp){//当n[j-1]>temp时，才进入循环进行判断
while(j>=1&&n[j-1]>temp){
n[j]=n[j-1];
j--;
}
}
n[j]=temp;
}
return n;
}
}
-
希尔排序（从小到大）
基本原理：先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序后”，最后再对所有元素进行一次直接插入排序。
public class ShellSort {
public static void sort(int[]n){
int len=n.length;
int d=len/2;//初始步长
int j=0;
while(d>0){
for(int i=d;i<n.length;i++){
//从索引值为d的数组元素开始，依次与子序列中前面的元素进行对比
int temp=n[i];
for(j=i;j>=d;j-=d){//对比的索引减量为d
if(n[j-d]>temp){
n[j]=n[j-d];
}else{
break;
}
}
n[j]=temp;
}
d=d/2;
}
}
}
选择排序：
-
选择排序
基本原理：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止。
public class SelectSort {
public static int[] sort(int[] n){
int temp=0;
for(int i=0;i<n.length-1;i++){
int flag=i;
temp=n[i];
for(int j=i+1;j<n.length;j++){
if(temp>n[j]){
temp=n[j];
flag=j;
}
}
if(flag!=i){
n[flag]=n[i];
n[i]=temp;
}
}
return n;
}
}
-
堆排序
基本思想：对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的最后一个元素与堆顶元素（即二叉树的根节点）进行交换后，堆的最后一个元素即为最大记录；接着将前（n-1）个元素（即不包括最大记录）重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最小记录，此时可得到一个有序序列。
public class HeapSort {
//排序
public static void sort(int[]n){
for(int i=0;i<n.length-1;i++){
buildMaxHeap(n, n.length-1-i);//循环建堆
exchange(n, 0, n.length-1-i);//交换堆顶与堆中最后一个元素
System.out.println(Arrays.toString(n));
}
}
//建立大顶堆
public static void buildMaxHeap(int[]n,int lastindex){
//从最后一个结点的父节点开始构建
for(int i=(lastindex-1)/2;i>=0;i--){
while(2*i+1<=lastindex){//判断i结点是否有子结点
int k=2*i+1;//i结点的左子树
int max=k;//标记最大子树的索引值
int temp=n[k];//标记最大子树的值
if(k<lastindex){//判断i结点是否有右子树
if(n[k]<n[k+1]){
temp=n[k+1];
max=k+1;
}
}
if(n[max]>n[i]){//子结点的值大于父结点
exchange(n,i,max);
k=max;
}else{
break;
}
}
}
}
//交换数组中的两个元素
public static void exchange(int[]n,int i,int j ){
int temp=0;
temp=n[i];
n[i]=n[j];
n[j]=temp;
}
}
交换排序：
-
冒泡排序
基本思想：（由小到大）对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和换位后，n个记录中的最大记录将位于第n位；然后对前（n-1）个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个为止。
public class BubbleSort {
public static int[] sort(int[] n){
if(n.length<=0){
return null;
}
int temp=0;
for(int i=0;i<n.length-1;i++){//比较的趟数
for(int j=0;j<n.length-i-1;j++){//每趟比较的次数
//按从小到大的顺序排序
if(n[j]>n[j+1]){
temp=n[j];
n[j]=n[j+1];
n[j+1]=temp;
}
}
}
return n;
}
}
-
快速排序
基本思想：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。
public class QuickSort {
public static void sort(int[]n,int start,int end){
int flag=0;//对数组进行分解的基准值的索引
if(start<end){
flag=partition(n,start,end);
sort(n,start,flag-1);//递归对基准值左边的子数组进行排序
sort(n,flag+1,end);//递归对基准值右边的子数组进行排序
}
}
public static int partition(int[]n,int start,int end){
int temp=n[start];//将数组最左边的值设置为基准值
while(start<end){
while(start<end&&temp<n[end]){//从右往左找到第一个比基准值小的值
end--;
}
if(start<end){
n[start]=n[end];//将第一个比基准值小的值赋值给start位置索引
start++;//start指针前移一个位置
}
while(start<end&&temp>n[start]){//从左往右找到第一个比基准值大的值
start++;
}
if(start<end){
n[end]=n[start];//将第一个比基准值大的值赋值给end位置索引
end--;//end指针后移一个位置
}
}
//此时start=end
n[end]=temp;
return end;
}
}
-
归并排序
基本思想：对于给定的一组记录（假设共有n个记录），首先将每两个相邻的长度为1的子序列进行归并，得到n/2（向上取整）个长度为2或1的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列。
public class MergeSort {
public static void sort(int[] n,int left,int right){
if(left<right){
int mid=(left+right)/2;//计算数组中间元素索引位置
sort(n, left, mid);//对左半部分进行递归排序
sort(n, mid+1, right);//对右半部分进行递归排序
merge(n, left, mid, right);//合并
}
}
public static void merge(int[]n,int start,int mid,int end){
int[] temp=new int[n.length];//定义一个临时数组用于存放排好序的数组元素
int p=start;
int k=start;
int left=start;//左指针
int right=mid+1;//右指针
while(left<=mid&&right<=end){
if(n[left]>n[right]){
temp[p++]=n[left++];
}else{
temp[p++]=n[right++];
}
}
//将剩余元素填充到temp数组中
while(left<=mid){
temp[p++]=n[left++];
}
while(right<=end){
temp[p++]=n[right++];
}
//将temp数组中的元素复制到数组n中
while(k<=end){
n[k]=temp[k];
k++;
}
}
}
-
基数排序
基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位比较短的数前面补零。然后，从最低位开始，依次进行依次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
public class RadixSort {
public static void sort(int[]n){
//获取数组中最大的数
int temp=0;
for(int i=0;i<n.length;i++){
if(n[i]>temp){
temp=n[i];
}
}
//得到需要比较的次数
int count=0;
while(temp>0){
temp=temp/10;
count++;
}
//创建十个数组
List<ArrayList<Integer>> queue=new ArrayList<ArrayList<Integer>>();
for(int i=0;i<10;i++){
ArrayList<Integer> list=new ArrayList<Integer>();
queue.add(list);
}
//每一数组中元素的排序
for(int i=0;i<count;i++){
for(int j=0;j<n.length;j++){
//获取数值中的各位数字
int x=n[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
ArrayList<Integer> list1=queue.get(x);//获取queue中索引值为x的集合
list1.add(n[j]);//将原数组中的数值添加到集合中
}
//按照数组中值的各位大小进行排序
int num=0;//元素计数器
for(int k=0;k<10;k++){
while(queue.get(k).size()>0){//遍历数组中各个集合中的元素值
ArrayList<Integer>list2=queue.get(k);//获取索引值k所对应的集合
n[num]=list2.get(0);//依次移除集合中的各个元素
list2.remove(0);
num++;
}
}
}
}
}
