- 前言
- 一、交换排序
- 冒泡排序
- 快速排序
- 二、选择排序
- 简单选择排序
- 堆排序
- 三、插入排序
- 直接插入排序
- 希尔排序
- 四、归并排序
- 四、基数排序
重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
public class Main {
public static void main(String[] args) {
int arr[] = {28,6,37,5,9,35,34,7,4};
for(int i=arr.length-1;i>0;i--){
int temp = 0;
for(int j=0;j<=i-1;j++){
if(arr[j]>arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
System.out.print(Arrays.toString(arr));
}
}
快速排序
1:
public class Main {
public static void quickSort(int arr[],int low,int high){
//如果过low>high说明全部排完,则返回
if(low>high)
return;
int l = low ;
int r = high;
int temp = arr[low];
while(l
//注意,必须先遍历与选取分界值想反的方向。比如[7, 6, 4, 5, 9],以左为分界值,先遍历左就会出现错误
//先从右遍历,直到右边出现比分界值小的数
while(arr[r]>=temp&&l
int t = arr[l];
arr[l] = arr[r];
arr[r] = t;
}
}
//目前,l和r相同,分界值位置始终没变,将分界值与l和r指向的数交换
//交换后l和r指向的数就是分界值,分界值左边的数都比它小,右边都比它大
arr[low]=arr[l];
arr[l]=temp;
//再对分界值左边和右边的数组分别进行排序
quickSort(arr, low, r-1);
quickSort(arr, r+1, high);
}
public static void main(String[] args) {
int arr[] = {28,6,37,5,9,35,34,7,4};
//传入待排序数组,i和j。默认key(分界值为arr[0])
quickSort(arr,0,arr.length-1);
System.out.print(Arrays.toString(arr));
}
}
二、选择排序
简单选择排序
第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。
public class Main {
public static void main(String[] args) {
int arr[] = {28,6,37,5,9,35,34,7,4};
for(int i=0;i
int temp = 0;
for(int j=i+1;j
if(arr[i]>arr[j])
{
temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
System.out.print(Arrays.toString(arr));
}
}
堆排序
public class Main {
public static void heapSort(int x[],int temp,int length){
int left = temp*2+1;
int min = x[temp];
while(left
if((left+1)=x[left])
break;
x[temp] = x[left];
temp = left;
left = left*2+1;
}
x[temp]=min;
}
public static void main(String[] args) {
int arr[] = {28,6,37,5,9,35,34,7,4};
for(int i=(arr.length-1-1)/2;i>=0;i--)
heapSort(arr,i,arr.length);
for(int i=arr.length-1;i>=0;i--){
int temp = arr[i];
arr[i]=arr[0];
arr[0] = temp;
heapSort(arr, 0,i);
}
System.out.print(Arrays.toString(arr));
}
}
三、插入排序
直接插入排序
public class Main {
public static void main(String[] args) {
int arr[] = {28,6,37,5,9,35,34,7,4};
for(int i=0;i
int value = arr[i+1];
int j;
for(j=i;j>=0&&value
希尔排序
public class Main {
public static void main(String[] args) {
int arr[] = {28,6,37,5,9,35,34,7,4};
for(int step = arr.length/2;step>0;step=step/2){
for(int i=step;i
int value = arr[i];
int j;
for(j=i-step;j>=0&&value
arr[j+step] = arr[j];
}
arr[j+step]=value;
}
}
System.out.print(Arrays.toString(arr));
}
}
四、归并排序
public class Main {
public static void merge(int arr[]){
if(arr.length<2)
return ;
int mid = arr.length/2;
int left[] = Arrays.copyOfRange(arr, 0, mid);
int right[] = Arrays.copyOfRange(arr, mid, arr.length);
mergeSort(left,right);
}
public static int[] mergeSort(int left[],int right[]){
int result[] = new int[left.length+right.length];
for(int index = 0,i = 0,j = 0;index
if(i>=left.length)
result[index] = right[j++];
else if(j>=right.length)
result[index] = left[i++];
else if(left[i]>right[j])
result[index] = right[j++];
else
result[index] = left[i++];
}
return result;
}
public static void main(String[] args) {
int arr[] = {28,6,37,5,9,35,34,7,4};
System.out.println(Arrays.toString(merge(arr)));
}
}
四、基数排序
public class Main {
public static void radixSort(int arr[]){
int result[] = new int[arr.length];
int num[] = new int[10];
int N = 0;
int max = arr[0];
for(int i=1;i
if(arr[i]>max)
max=arr[i];
}
while(max!=0){
N++;
max/=10;
}
for(int i=0;i
int division = (int)Math.pow(10, i);
for(int j=0;j
num[arr[j]/division%10]++;
}
for(int j = 1;j=0;j--){
int t = arr[j]/division%10;
result[--num[t]]=arr[j];
}
System.arraycopy(result, 0, arr, 0, arr.length);
Arrays.fill(num, 0);
}
}
public static void main(String[] args) {
int arr[] = {28,6,37,5,9,35,34,7,4};
radixSort(arr);
System.out.print(Arrays.toString(arr));
}
}



