|
//希尔排序（希尔排序可以说成是选择排序的优化）
public class Xr {
public static void main(String[] args) {
?? ?int[] arr={4,5,3,9,5,7};
?? ?xr(arr);
?? ?System.out.println(Arrays.toString(arr));
}
public static void xr(int[] arr) {
?? ?for(int gap=arr.length/2;gap>0;gap /=2) {
?? ??? ?for(int i=gap;i<arr.length;i++) {
?? ??? ??? ?for(int j=i-gap;j>=0;j-=gap) {
?? ??? ??? ??? ?if(arr[j]>arr[j+gap]) {
?? ??? ??? ??? ?int?? ?temp=arr[j];
?? ??? ??? ??? ?arr[j]=arr[j+gap];
?? ??? ??? ??? ?arr[j+gap]=temp;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
}
//基数排序
public class Tong {
?? ?public static void main(String[] args) {
?? ??? ?int[] arr= {45,4,123};
?? ??? ?tong(arr);
?? ??? ?System.out.println(Arrays.toString(arr));
?? ?}
?? ?public static void tong(int[] arr) {
?? ??? ?//第一步：找出最大值
?? ??? ?int max=arr[0];
?? ??? ?for (int a = 0; a < arr.length; a++) {
?? ??? ??? ?if(arr[a]>max) {
?? ??? ??? ??? ?max=arr[a];
?? ??? ??? ?}
?? ??? ?}
?? ??? ?//第二步：找出最大的数值的长度
?? ??? ?int maxLength=(max+"").length();
?? ??? ?
?? ??? ?//第三步：进行桶排序
?? ??? ?//定义一个二位数组表示桶
?? ??? ?int[][] tong=new int[10][arr.length];
?? ??? ?//定义一个辅助数组表示每个桶的存放数量
?? ??? ?int[] fu=new int[10];
?? ??? ?int n=1;
?? ??? ?for (int i = 0; i < maxLength; i++) {
?? ??? ??? ?//将元素放入桶
?? ??? ??? ?for (int j = 0; j < arr.length; j++) {
?? ??? ??? ??? ?int zhi=arr[j]/n%10;
?? ??? ??? ??? ?tong[zhi][fu[zhi]]=arr[j];
?? ??? ??? ??? ?fu[zhi]++;
?? ??? ??? ?}
?? ??? ??? ?int index=0;
?? ??? ??? ?for (int c = 0; c < fu.length; c++) {
?? ??? ??? ??? ?if(fu[c]!=0) {
?? ??? ??? ??? ??? ?for(int k =0;k<fu[c];k++) {
?? ??? ??? ??? ??? ??? ?arr[index++]=tong[c][k];
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}?
?? ??? ??? ??? ?//将辅助数组中数据置空
?? ??? ??? ??? ?fu[c]=0;
?? ??? ??? ?}
?? ??? ??? ?n=n*10;
?? ??? ?}
?? ?}
}
堆排序
package com.qcby2;
import java.util.Arrays;
//堆排序
public class Dui {
public static void main(String[] args) {
?? ?int[] arr={2,4,5,3,9,5,1,999,54,48,7};
?? ?heapSoet(arr);
?? ?System.out.println(Arrays.toString(arr));
}
/**
?* ?创建堆
?* @param arr
?*/
public static ?void heapSoet(int[] arr){
? ? for (int i = (arr.length -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);
? ? }
}
/**
?* 调整大顶堆的方法
?* @param arr
?* @param parent ? 父指针
?* @param length ? 数组长度
?*/
public static void HeapSort(int[] arr,int parent,int length){
? ? int temp = arr[parent];// 定义出父节点的值
? ? int lChild = 2 * parent +1; ?// 如果当前节点不是叶子节点，那么一定有左子树(完全二叉树的性质)
? ? while (lChild < length){
? ? ? ? ? ? // 右孩子
? ? ? ? ? ? int rChild = lChild +1;
? ? ? ? ? ? //判断是否有右孩子节点，如果有我们让右孩子节点的值和左孩子节点的值进行对比
? ? ? ? ? ? if(rChild < length && arr[lChild] < arr[rChild]){
? ? ? ? ? ? ? ? lChild ++;
? ? ? ? ? ? }
? ? ? ? ? ? // 判断父节点的值和左指针的值
? ? ? ? ? ? if(temp >= arr[lChild]){
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? // 把孩子节点的值付给父节点
? ? ? ? ? ? arr[parent] = arr[lChild];
? ? ? ? ? ? parent = lChild;
? ? ? ? ? ? lChild = 2 * lChild +1;
? ? ? ? ? ?
? ? }
? ? arr[parent] = temp;
}
}
//归并排序
package com.qcby2;
import java.util.Arrays;
public class Gui {
public static void main(String[] args) {
?? ?int[] arr = new int[]{2,4,5,3,87,45};
? ? Sort(arr,0,arr.length-1);
? ? System.out.println(Arrays.toString(arr));
}
?? ? public static void Sort(int[] arr,int left,int right){
?? ? ? ? ? ?if(left >= right){
?? ? ? ? ? ? ? ?return;
?? ? ? ? ? ?}
?? ? ? ? ? ?int mid = (left + right) /2;
?? ? ? ? ? ?// 先递归左边
?? ? ? ? ? ?Sort(arr,left,mid);
?? ? ? ? ? ?// 在递归右边
?? ? ? ? ? ?Sort(arr,mid+1,right);
?? ? ? ? ? ?System.out.println(Arrays.toString(arr));
?? ? ? ? ? ?merge(arr,left,mid,right);
?? ? ? ?}
?? ? ? ?//合并
?? ? ? ?public static void merge(int[] arr,int left,int mid,int right){
?? ? ? ? ? ?// 定义指针s1
?? ? ? ? ? ?int s1 = left;
?? ? ? ? ? ?// 定义指针s2
?? ? ? ? ? ?int s2 =mid+1;
?? ? ? ? ? ?// 定义临时数组
?? ? ? ? ? ?int[] temp = new int[right - left +1];
?? ? ? ? ? ?int index =0; //临时数组的指针
?? ? ? ? ? ?//判断数组大小，将数组放入到临时数组当中去
?? ? ? ? ? ?while (s1<= mid && s2<=right){
?? ? ? ? ? ? ? ?if(arr[s1] <= arr[s2]){
?? ? ? ? ? ? ? ? ? ?temp[index] = arr[s1];
?? ? ? ? ? ? ? ? ? ?index ++;
?? ? ? ? ? ? ? ? ? ?s1 ++;
?? ? ? ? ? ? ? ?}else {
?? ? ? ? ? ? ? ? ? ?temp[index] = arr[s2];
?? ? ? ? ? ? ? ? ? ?index ++;
?? ? ? ? ? ? ? ? ? ?s2 ++;
?? ? ? ? ? ? ? ?}
?? ? ? ? ? ?}
?? ? ? ? ? ?// 判断 s1所值得数组当中有没有数据
?? ? ? ? ? ?while (s1 <= mid){
?? ? ? ? ? ? ? ?temp[index] = arr[s1];
?? ? ? ? ? ? ? ?index ++;
?? ? ? ? ? ? ? ?s1 ++;
?? ? ? ? ? ?}
?? ? ? ? ? ?// 判断 s2所值得数组当中有没有数据
?? ? ? ? ? ?while (s2 <=right){
?? ? ? ? ? ? ? ?temp[index] = arr[s2];
?? ? ? ? ? ? ? ?index ++;
?? ? ? ? ? ? ? ?s2 ++;
?? ? ? ? ? ?}
?? ? ? ? ? ?//将临时数组当中的数据放回原数组
?? ? ? ? ? ?for (int j =0;j<temp.length;j++){
?? ? ? ? ? ??? ?System.out.println(left);
?? ? ? ? ? ? ? ?arr[j + left] = temp[j];
?? ? ? ? ? ?}
?? ? ? ?}
}
?
|