一、冒泡排序
public class 冒泡排序 {
public static void main(String[] args) {
int[] a=new int[10];
for (int i = 0; i < 10; i++) {
a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
System.out.print(a[i]+" ");
}
System.out.println("\n");
for (int i = a.length-1; i > 0; i--) {
boolean flag=true;// 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成
for (int j = 0; j < i; j++) {
if(a[j]>a[j+1]){
int temp = a[j];
a[j]=a[j+1];
a[j+1]=temp;
flag=false;
}
}
if (flag) {
break;
}
}
for (int i = 0; i < 10; i++) {
System.out.print(a[i] + " ");
}
}
}
二、选择排序
public class 选择排序 {
public static void main(String[] args) {
int[] a=new int[10];
for (int i = 0; i < 10; i++) {
a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
System.out.print(a[i]+" ");
}
System.out.println("\n");
for (int i = 0; i < a.length-1; i++) {
int min=i;
for (int j = i+1; j <a.length ; j++) {
// 记录目前能找到的最小值元素的下标
if(a[j]<a[min]){
min=j;
}
}
if (i!=min) {
int temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
for (int i = 0; i < 10; i++) {
System.out.print(a[i] + " ");
}
}
}
三、插入排序
public class 插入排序 {
public static void main(String[] args) {
int[] a=new int[10];
for (int i = 0; i < 10; i++) {
a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
System.out.print(a[i]+" ");
}
System.out.println("\n");
Insertsort(a);//插入排序
for (int i = 0; i < 10; i++) {
System.out.print(a[i] + " ");
}
}
public static void Insertsort(int[] a){
for (int i = 1; i < a.length; i++) {
int number=a[i];
int j;
for (j=i;j>0&&number<a[j-1];j--) {
// 从已经排序的序列最右边的开始比较,找到比其小的数
a[j]=a[j-1];
}
if (j!=i) {
a[j]=number;
}
}
}
}
四、折半插入排序
public class 折半插入排序 {
public static void main(String[] args) {
int[] a=new int[10];
for (int i = 0; i < 10; i++) {
a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
System.out.print(a[i]+" ");
}
System.out.println("\n");
HalveInsertsort(a);//折半插入排序
for (int i = 0; i < 10; i++) {
System.out.print(a[i] + " ");
}
}
public static void HalveInsertsort(int[] a){
for (int i = 1; i < a.length; i++) {
int number=a[i];
int low=0,high=i;
while (low<=high) {
int mid=low+(high-low)/2;
if (number<a[mid]) {
high=mid-1;
} else if (number>a[mid]) {
low=mid+1;
}else{
low=mid;
break;
}
}
int k;
for(k=i;k>low;k--){
a[k]=a[k-1];
}
a[k]=number;
}
}
}
五、希尔排序
//希尔排序:希尔排序是基于插入排序而提出改进方法的
public class 希尔排序 {
public static void main(String[] args) {
int[] a=new int[10];
for (int i = 0; i < 10; i++) {
a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
System.out.print(a[i]+" ");
}
System.out.println("\n");
Shell_Sort(a,a.length);//希尔排序
for (int i = 0; i < 10; i++) {
System.out.print(a[i] + " ");
}
}
public static void Shell_Sort(int[] a,int n){
int increment=n;//增量
do{
increment=increment/3+1;
ShellPass(increment,n,a);
}while (increment>1);
}
public static void ShellPass(int d,int n,int[] a){
int j;
for (int i=d;i<n;i++) {
if (a[i] < a[i - d]) {
int number = a[i];
for (j = i - d; j >= 0 && a[j] > number; j -= d) {
a[j + d] = a[j];
}
a[j + d] = number;
}
}
}
}
六、快速排序
//快速排序算是在冒泡排序基础上的递归分治法
public class 快速排序 {
public static void main(String[] args) {
int[] a=new int[10];
for (int i = 0; i < 10; i++) {
a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
System.out.print(a[i]+" ");
}
System.out.println("\n");
QKsort(a,0,a.length-1);
for (int i = 0; i < 10; i++) {
System.out.print(a[i] + " ");
}
}
public static void QKsort(int[] a,int low,int high){
int pos;
if(low<high){
pos=QKpass(a,low,high);
QKsort(a,low,pos-1);
QKsort(a,pos+1,high);
}
}
public static int QKpass(int[] a,int low,int high){
int x=a[low];
while (low<high) {
while (low<high&&a[high]>x) {high--;}
if (low<high) {a[low]=a[high];}
while (low<high&&a[low]<x) {low++;}
if (low<high) {a[high]=a[low];}
}
a[low]=x;
return low;
}
}
七、归并排序
public class 归并排序 {
public static void main(String[] args) {
int[] a=new int[10];
for (int i = 0; i < 10; i++) {
a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
System.out.print(a[i]+" ");
}
System.out.println("\n");
MergeSort(a,0,a.length-1);//归并排序
for (int i = 0; i < 10; i++) {
System.out.print(a[i] + " ");
}
}
public static void MergeSort(int[] a,int low,int high){
if(low<high){
int mid=low+(high-low)/2;
MergeSort(a,low,mid);
MergeSort(a,mid+1,high);
Merge(a,low,mid,high);
}
}
public static void Merge(int[] a,int low,int mid,int high){
int[] temp=new int[a.length];
int i=low,j=mid+1,k=low;
while (i<=mid&&j<=high) {
if(a[i]<a[j]){temp[k]=a[i];i++;}
else{temp[k]=a[j];j++;}
k++;
}
while (i<=mid) {temp[k]=a[i];i++;k++;}
while (j<=high) {temp[k]=a[j];j++;k++;}
for (int i1 : temp) {
System.out.print(i1+" ");
}
System.out.print('\n');
for (int e = low; e <= high; e++) {
a[e]=temp[e];
}
}
}
八、堆排序
import java.util.Arrays;
public class HeapSort {
public static void main(String []args){
int []arr = {7,6,7,11,5,12,3,0,1};
System.out.println("排序前:"+Arrays.toString(arr));
sort(arr);
System.out.println("排序前:"+Arrays.toString(arr));
}
public static void sort(int []arr){
//1.构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子结点从下至上,从右至左调整结构
adjustHeap(arr,i,arr.length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对堆进行调整
}
}
// 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始,也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
//交换元素
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
参考来源:https://blog.csdn.net/qq_36186690/article/details/82505569
九、基数排序
public class RadixSort {
public static void main(String[] args) {
int[] arr = {63, 157, 189, 51, 101, 47, 141, 121, 157, 156,
194, 117, 98, 139, 67, 133, 181, 12, 28, 0, 109};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 高位优先法
*
* @param arr 待排序列,必须为自然数
*/
private static void radixSort(int[] arr) {
//待排序列最大值
int max = arr[0];
int exp;//指数
//计算最大值
for (int anArr : arr) {
if (anArr > max) {
max = anArr;
}
}
//从个位开始,对数组进行排序
for (exp = 1; max / exp > 0; exp *= 10) {
//存储待排元素的临时数组
int[] temp = new int[arr.length];
//分桶个数
int[] buckets = new int[10];
//将数据出现的次数存储在buckets中
for (int value : arr) {
//(value / exp) % 10 :value的最底位(个位)
buckets[(value / exp) % 10]++;
}
//更改buckets[i],
for (int i = 1; i < 10; i++) {
buckets[i] += buckets[i - 1];
}
//将数据存储到临时数组temp中
for (int i = arr.length - 1; i >= 0; i--) {
temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
buckets[(arr[i] / exp) % 10]--;
}
//将有序元素temp赋给arr
System.arraycopy(temp, 0, arr, 0, arr.length);
}
}
}