八大排序算法java实现

随着计算机技术的不断发展，排序算法也不断地被改进和优化。目前常用的排序算法有八种，分别为冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序、计数排序和桶排序。在本文中，我们将从多个角度分析这些排序算法，并提供Java实现。

1. 冒泡排序

冒泡排序是一种基本的排序算法，其核心思想是通过比较相邻元素的大小来进行排序。在每一轮排序中，将相邻元素进行比较、交换，将最大的元素逐步“冒泡”到数组顶端。当某一轮排序没有进行任何交换时，表示已经排好序，可以结束排序。

Java代码实现：

```java

public static void bubbleSort(int[] arr){

int temp;

for(int i=0;i

for(int j=0;j

if(arr[j]>arr[j+1]){

temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

}

}

}

```

2. 插入排序

插入排序的思想是将一个数组分成两部分，将后面部分的元素依次插入前面的有序部分中。首先假设第一个元素为已排序部分，然后从第二个元素开始，每次取出一个元素插入到前面的有序部分中，直到整个数组排序完成。

Java代码实现：

```java

public static void insertionSort(int[] arr){

int temp,j;

for(int i=1;i

temp=arr[i];

j=i-1;

while(j>=0&&temp

arr[j+1]=arr[j];

j--;

}

arr[j+1]=temp;

}

}

```

3. 选择排序

选择排序是一种简单的排序算法，其思想是每次从未排序的元素中选出一个最小值，放到已排序部分的末尾。从未排序部分中选出最小值可以使用线性查找的方法。

Java代码实现：

```java

public static void selectionSort(int[] arr){

int min,temp;

for(int i=0;i

min=i;

for(int j=i+1;j

if(arr[j]

min=j;

}

if(min!=i){

temp=arr[min];

arr[min]=arr[i];

arr[i]=temp;

}

}

}

```

4. 快速排序

快速排序是一种分治算法，其核心思想是将一个数组分成两个子数组，然后递归地对两个子数组进行排序，最终将这两个子数组合并成一个有序数组。在每一次排序中，选择一个标准元素（通常为数组的第一个元素），将数组中小于标准元素的放在左边，大于标准元素的放在右边。

Java代码实现：

```java

public static void quickSort(int[] arr,int left,int right){

if(left>=right)

return;

int key=arr[left];

int i=left,j=right;

while(i

while(i =key){

j--;

}

if(i

arr[i]=arr[j];

i++;

}

while(i

i++;

}

if(i

arr[j]=arr[i];

j--;

}

}

arr[i]=key;

quickSort(arr,left,i-1);

quickSort(arr,i+1,right);

}

```

5. 归并排序

归并排序也是一种分治算法，其核心思想是将一个数组分成两个子数组，然后递归地对两个子数组进行排序，最终将这两个子数组合并成一个有序数组。在归并阶段，定义三个指针来比较两个子数组的元素，将较小的元素放入合并后的数组中。

Java代码实现：

```java

public static void mergeSort(int[] arr,int left,int right,int[] temp){

if(left

int mid=(left+right)/2;

mergeSort(arr,left,mid,temp);

mergeSort(arr,mid+1,right,temp);

merge(arr,left,mid,right,temp);

}

}

public static void merge(int[] arr,int left,int mid,int right,int[] temp){

int i=left;

int j=mid+1;

int t=0;

while(i<=mid&&j<=right){

if(arr[i]<=arr[j]){

temp[t++]=arr[i++];

}else{

temp[t++]=arr[j++];

}

}

while(i<=mid){

temp[t++]=arr[i++];

}

while(j<=right){

temp[t++]=arr[j++];

}

t=0;

while(left<=right){

arr[left++]=temp[t++];

}

}

```

6. 堆排序

堆排序利用了完全二叉树的性质，将一个数组看作一棵完全二叉树。首先将数组构建成一个大顶堆，然后将堆顶元素和数组末尾元素交换，然后对除末尾元素以外的部分重新进行堆排序。

Java代码实现：

```java

public static void heapSort(int[] arr){

for(int i=(arr.length/2-1);i>=0;i--){

adjustHeap(arr,i,arr.length);

}

int temp;

for(int i=arr.length-1;i>0;i--){

temp=arr[i];

arr[i]=arr[0];

arr[0]=temp;

adjustHeap(arr,0,i);

}

}

public static void adjustHeap(int[] arr,int i,int length){

int temp=arr[i];

for(int k=i*2+1;k

if(k

k++;

}

if(arr[k]>temp){

arr[i]=arr[k];

i=k;

}else{

break;

}

}

arr[i]=temp;

}

```

7. 计数排序

计数排序是一种非比较排序算法，其核心思想是统计每个元素出现的次数，然后计算出每个元素前面有多少个元素。最后将元素放入一个新的数组中，将元素插入到正确的位置。

Java代码实现：

```java

public static void countSort(int[] arr){

int max=arr[0],min=arr[0];

for(int i=1;i

if(arr[i]>max){

max=arr[i];

}

if(arr[i]

min=arr[i];

}

}

int[] count=new int[max-min+1];

for(int i=0;i

count[arr[i]-min]++;

}

for(int i=1;i

count[i]+=count[i-1];

}

int[] temp=new int[arr.length];

for(int i=arr.length-1;i>=0;i--){

temp[--count[arr[i]-min]]=arr[i];

}

for(int i=0;i

arr[i]=temp[i];

}

}

```

8. 桶排序

桶排序是一种分配排序算法，其核心思想是将元素分配到不同的桶中，然后对每个桶中的元素进行排序，最后将各个桶的结果合并起来。通过调整桶的数量和大小可以平衡时间和空间的消耗。

Java代码实现：

```java

public static void bucketSort(int[] arr){

int max=arr[0],min=arr[0];

for(int i=1;i

if(arr[i]>max){

max=arr[i];

}

if(arr[i]

min=arr[i];

}

}

int bucketSize=Math.max(1,(max-min)/arr.length+1);

int bucketCount=(max-min)/bucketSize+1;

ArrayList[] buckets=new ArrayList[bucketCount];

for(int i=0;i

buckets[i]=new ArrayList ();

}

for(int i=0;i

int index=(arr[i]-min)/bucketSize;

buckets[index].add(arr[i]);

}

int k=0;

for(int i=0;i

if(buckets[i]==null||buckets[i].size()==0)

continue;

int[] temp=new int[buckets[i].size()];

for(int j=0;j

temp[j]=(int)buckets[i].get(j);

}

insertionSort(temp);

for(int j=0;j

arr[k++]=temp[j];

}

}

}

```