八大排序算法java代码

时间:2023-12-20 16:53:14

1.冒泡排序

  public static void main(String[] args) {
int[] arr = {1,4,2,9,5,7,6};
System.out.println("排序前:"+Arrays.toString(arr));
bubbleSort(arr);
System.out.println("冒泡排序后:"+Arrays.toString(arr));
} static void bubbleSort(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}

2.快速排序

  public static void main(String[] args) {
int[] arr = {1,4,2,9,5,7,6};
System.out.println("排序前:"+Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
System.out.println("快速排序后:"+Arrays.toString(arr));
} static void quickSort(int[] arr,int left,int right){
if(left>=right) return;//如果只有一个元素,不用遍历
int i=left,j=right,temp=arr[left];
while(i<j){
while(i<j && arr[j]>=temp) j--;
arr[i]=arr[j];//遇见小的移动
while(i<j && arr[i]<=temp) i++;
arr[j]=arr[i];
}
arr[i]=temp;//i==j
quickSort(arr,left,i-1);
quickSort(arr,i+1,right);
}

3.简单选择排序

  public static void main(String[] args) {
int[] arr = {1,4,2,9,5,7,6};
System.out.println("排序前:"+Arrays.toString(arr));
selectSort(arr);
System.out.println("选择排序后:"+Arrays.toString(arr));
} static void selectSort(int[] arr){
int min = 0;
for(int i=0;i<arr.length-1;i++){
min = i;
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[min])
min = j;
}
if(min!=i){
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}

4.直接插入排序

  public static void main(String[] args) {
int[] arr = {1,4,2,9,5,7,6};
System.out.println("排序前:"+Arrays.toString(arr));
shellSort(arr);
System.out.println("希尔排序后:"+Arrays.toString(arr));
} static void shellSort(int[] arr){
for(int increment=arr.length/2;increment>0;increment/=2){//增量循环变更
for(int i=increment;i<arr.length;i++){
for(int j=i-increment;j>=0;j-=increment){
if(arr[j]>arr[j+increment]){
int temp = arr[j];
arr[j] = arr[j+increment];
arr[j+increment] = temp;
}
}
}
}
}

5.希尔排序

  public static void main(String[] args) {
int[] arr = {1,4,2,9,5,7,6};
System.out.println("排序前:"+Arrays.toString(arr));
shellSort(arr);
System.out.println("希尔排序后:"+Arrays.toString(arr));
} static void shellSort(int[] arr){
for(int increment=arr.length/2;increment>0;increment/=2){//增量循环变更
for(int i=increment;i<arr.length;i++){
for(int j=i-increment;j>=0;j-=increment){
if(arr[j]>arr[j+increment]){
int temp = arr[j];
arr[j] = arr[j+increment];
arr[j+increment] = temp;
}
}
}
}
}

6.归并排序

  public static void main(String[] args) {
int[] arr = {1,4,2,9,5,7,6};
System.out.println("排序前:"+Arrays.toString(arr));
mergeSort(arr);
System.out.println("归并排序后:"+Arrays.toString(arr));
} static void mergeSort(int[] arr){
sort(arr,0,arr.length-1);
} static void sort(int[] arr,int low,int high){
int mid = (low+high)/2;
if(low<high){
sort(arr,low,mid);
sort(arr,mid+1,high);
merge(arr,low,mid,high);//归并
}
} static void merge(int[] arr,int low,int mid,int high){
int[] newArr = new int[high-low+1];
int i = low,j=mid+1,k=0;
while(i<=mid && j<=high){
if(arr[i]<arr[j]){
newArr[k++] = arr[i++];
}else{
newArr[k++] = arr[j++];
}
} //左边剩余移入数组
while(i<=mid){
newArr[k++] = arr[i++];
}
//右边剩余移入数组
while(j<=high){
newArr[k++] = arr[j++];
}
// 把新数组中的数覆盖原数组
for(k=0;k<newArr.length;k++){
arr[k+low] = newArr[k];
}
}

7.基数/桶排序

  public static void main(String[] args) {
int[] arr = {1,4,2,9,5,7,6};
System.out.println("排序前:"+Arrays.toString(arr));
radixSort(arr);
System.out.println("基数排序后:"+Arrays.toString(arr));
} static void radixSort(int[] arr){
sort(arr,0,arr.length-1,1);
} //digit元素最高位数
static void sort(int[] arr,int low,int high,int digit){
int radix = 10;//0~9 基数
int[] count = new int[radix];//确定桶中每一个基数的索引位置
int[] bucket = new int[high-low+1];//桶 用数组表示
for(int d=1;d<=digit;d++){
// 置空各个桶索引
for (int i = 0; i < radix; i++) {
count[i] = 0;
}
//统计桶数据个数
for (int i = low,j=0; i <=high; i++) {
j = getDigit(arr[i], d);
count[j]++;
}
//确定桶的右边索引
for (int i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
//数据入桶
for (int i = high,j=0; i >= low; i--) {
j = getDigit(arr[i], d);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
//赋值原数组
for (int i = 0; i <= high; i++) {
arr[i+low] = bucket[i];
}
}
} //得到第几位数字
static int getDigit(int x, int d) {
return ((x / (int)Math.pow(10, d-1)) % 10);
}

8.堆排序

public static void main(String[] args) {
int[] arr = {1,4,2,9,5,7,6};
System.out.println("排序前:"+Arrays.toString(arr));
heapSort(arr);
System.out.println("堆排序后:"+Arrays.toString(arr));
} static void heapSort(int[] arr){
int len = arr.length-1;
//建立大顶堆
for(int i=len/2; i>=0; i--)
{
heapAdjust(arr,i,len);
}
//进行排序
for(int i=len; i>0; i--)
{
//最后一个元素和第一元素进行交换
int temp=arr[i];
arr[i] = arr[0];
arr[0] = temp;
//然后将剩下的无序元素继续调整为大顶堆
heapAdjust(arr,0,i-1);
} } static void heapAdjust(int[] arr,int low,int high){
int temp = arr[low];
//i结点左孩子和右孩子分别为2i+1和2i+2
for(int i=2*low+1;i<=high;i*=2){
if(i<high && arr[i]<arr[i+1]){//左右孩子比较大小
i++;
}
if(temp>arr[i])//左右孩子中最大值父亲结点比较大小
break;
arr[low]= arr[i];
low = i;
}
arr[low] = temp;
}

选择排序、快速排序、希尔排序、堆排序是不稳定的排序算法

冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法