1.冒泡排序
算法描述：
比较相邻的元素，如果前一个比后一个大，交换之。
第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
第二趟将第二大的数移动至倒数第二位
......
因此需要n-1趟；
public static void main(String[] args) {
int[] nums={6,5,4,3,2,1};
sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.println(nums[i]);
}
}
public static void sort(int[] nums){
//一定要记住最外层的循环为趟数
for(int i=0;i<nums.length;i++){
//为什么要减1，因为最后一个不需要比较了
for(int j=0;j<nums.length-i-1;j++){
//替换
if(nums[j]>nums[j+1]){
int temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}
}
2.选择排序
public static void main(String[] args) {
int[] nums={6,5,4,3,2,1};
sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.println(nums[i]);
}
}
public static void sort(int[] nums){
for(int i=0;i<nums.length-1;i++){
//定义一个变量，记录最小元素所在的索引
int min=i;
for(int j=i+1;j<nums.length;j++){
//需要比较最小索引min的值和j索引的值
if(nums[j]<nums[min]){
//这里只是找到了最小元素所在的索引位置；
min=j;
}
}
//找到了以后就会交换位置
int temp=nums[i];
nums[i]=nums[min];
nums[min]=temp;
}
}
3.插入排序
public static void main(String[] args) {
int[] nums={6,5,4,3,2,1};
sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.println(nums[i]);
}
}
public static void sort(int[] nums){
//外层for为趟数
for (int i = 0; i <nums.length-1 ; i++) {
//往前遍历
for(int j=i+1;j>0;j--){
//比较替换
if(nums[j]<nums[j-1]){
int temp=nums[j];
nums[j]=nums[j-1];
nums[j-1]=temp;
}
}
}
}
4.希尔排序
public static void main(String[] args) {
int[] nums={6,5,4,3,2,1};
sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.println(nums[i]);
}
}
public static void sort(int[] nums){
//根据数组的长度确定增长量h的值
int h=1;
while(h<nums.length/2){
h=2*h+1;
}
while(h>0){
//排序
//找待插入的元素
for(int i=h;i<nums.length;i++){
//把待插入的元素插入到有序数列
for(int j=i;j>=h;j=j-h){
//比较
if(nums[j]<nums[j-h]){
//换位置
int temp=nums[j];
nums[j]=nums[j-h];
nums[j-h]=temp;
}else{
//找到了合适的位置后结束循环
break;
}
}
}
//h减少
h=h/2;
}
}
5.归并排序
public static void main(String[] args) {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
mergerSort(a, 0, a.length-1);
System.out.println("排好序的数组：");
for (int e : a)
System.out.print(e+" ");
}
public static void mergerSort(int[] a,int start,int end){
if(start<end){//当子序列中只有一个元素时结束递归
int mid=(start+end)/2;//划分子序列
mergerSort(a, start, mid);//对左侧子序列进行递归排序
mergerSort(a, mid+1, end);//对右侧子序列进行递归排序
merger(a, start, mid, end);//合并
}
}
public static void merger(int[] a,int left,int mid,int right){
int []tmp=new int[a.length];//辅助数组
int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针
while(p1<=mid && p2<=right){
if(a[p1]<=a[p2])
tmp[k++]=a[p1++];
else
tmp[k++]=a[p2++];
}
while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
while(p2<=right) tmp[k++]=a[p2++];//同上
//复制回原素组
for (int i = left; i <=right; i++)
a[i]=tmp[i];
}
6.快速排序
public static void main(String[] args) {
int[] nums={6,5,4,3,2,1};
sort(nums,0,nums.length-1);
for (int i = 0; i < nums.length; i++) {
System.out.println(nums[i]);
}
}
public static void sort(int[] nums,int left,int right){
if(left>right){
return ;
}
// temp中存放基准数
int i=left,j=right;
int temp=nums[left];
while(i!=j){
// 顺序很重要，先从右边开始往左找，直到找到比base值小的数
while(j>i && nums[j]>=temp){
j--;
}
// 再从左往右边找，直到找到比base值大的数
while(j>i && nums[i]<=temp){
i++;
}
// 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置
if(i<j){
int cur=nums[i];
nums[i]=nums[j];
nums[j]=cur;
}
}
// 将基准数放到中间的位置（基准数归位）
nums[left]=nums[i];
nums[i]=temp;
// 递归，继续向基准的左右两边执行和上面同样的操作
// i的索引处为上面已确定好的基准值的位置，无需再处理
sort(nums,left,i-1);
sort(nums,i+1,right);
}
