验证中...
码云 Gitee IDE 全新上线——支持 Git 管理的轻量在线编码环境
Main.java
原始数据 复制代码
import java.util.Arrays;
public class Main {
/**
直接插入* 排序类
*
* @author zm
*/
public static void getInsertSort(int[] a) {
if (a == null || a.length == 0) {//判断数组是否为空
System.out.println("该数组为空!");
return;
}
int n = a.length;//将数组的长度赋给n是为了防止每次for循环中判断时都调用length方法影响性能
int temp;//放于for循环外面是为了防止重复创建变量
int j;
for (int i = 1; i < n; i++) {//排序的趟数
temp = a[i];//赋给temp是为了防止索引i之前的元素向后移动覆盖了索引i的元素
j = i - 1;
for (; j >= 0 && a[j] > temp; --j) {//将大于i位置元素的元素向后移
a[j + 1] = a[j];
}
a[j + 1] = temp;//找到i应该在的位置,将值放置此处
}
}
/**
* 希尔排序
*
* @param arrays 需要排序的序列
*/
public static void sort(int[] arrays) {
if (arrays == null || arrays.length <= 1) {
return;
}
//增量
int incrementNum = arrays.length / 2;
while (incrementNum >= 1) {
for (int i = 0; i < arrays.length; i++) {
//进行插入排序
for (int j = i; j < arrays.length - incrementNum; j = j + incrementNum) {
if (arrays[j] > arrays[j + incrementNum]) {
int temple = arrays[j];
arrays[j] = arrays[j + incrementNum];
arrays[j + incrementNum] = temple;
}
}
}
//设置新的增量
incrementNum = incrementNum / 2;
}
}
public static void sort1(int[] arr) {
// i表示希尔排序中的第n/2+1个元素(或者n/4+1)
// j表示希尔排序中从0到n/2的元素(n/4)
// r表示希尔排序中n/2+1或者n/4+1的值
int i, j, r, tmp;
// 划组排序
for (r = arr.length / 2; r >= 1; r = r / 2) {
for (i = r; i < arr.length; i++) {
tmp = arr[i];
j = i - r;
// 一轮排序
while (j >= 0 && tmp < arr[j]) {
arr[j + r] = arr[j];
j -= r;
}
arr[j + r] = tmp;
}
// System.out.println(i + ":" + Arrays.toString(arr));
}
}
/**
* @param args
*/
public static void selectionSort(int[] arr) {
//选择排序的优化
for (int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
int k = i;
for (int j = k + 1; j < arr.length; j++) {// 选最小的记录
if (arr[j] < arr[k]) {
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束,也就是找到本轮循环的最小的数以后,再进行交换
if (i != k) { //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
}
/**
* 冒泡排序
*
* @param arr
*/
public static void BubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {//外层循环控制排序趟数
for (int j = 0; j < arr.length - 1 - i; j++) {//内层循环控制每一趟排序多少次
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] a = {3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
getInsertSort(a);
System.out.print("1直接插入排序:");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
a = new int[]{3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
sort1(a);
System.out.println("");
System.out.print("2希尔排序 :");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
a = new int[]{3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
selectionSort(a);
System.out.println("");
System.out.print("3选择排序 :");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
a = new int[]{3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
// System.out.print(""+a[0]);
selectionSort(a);
System.out.println("");
System.out.print("4冒泡排序 :");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
a = new int[]{3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
// System.out.print(""+a[0]);
mergeSort(a, 0, a.length - 1);
System.out.println("");
System.out.print("5归并排序 :");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
a = new int[]{3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
int start = 0;
int end = a.length - 1;
sort(a, start, end);
System.out.println("");
System.out.print("6快速排序 :");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
a = new int[]{3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
HeapSort(a);
System.out.println("");
System.out.print("7堆排序 :");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
a = new int[]{3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
radixSort(a,100);
System.out.println("");
System.out.print("8基数排序 :");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
/***
*
*排序算法之归并排序(2路归并)
*
*/
public static void mergeSort(int[] a, int low, int high) {
if (low < high) {//递归结束条件
int mid = (low + high) / 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];
//这里把要排序数组copy一份,用来比较,原来的数组用来保存比较后的信息
for (int i = low; i <= high; i++) {
//注意这里copy时,下标是从low开始的,要是为了保证copy的数组下标与目标数组下标一致,这样是为了方便后面的比较的下标操作
temp[i] = a[i];
//当然copy的数组保存时也可以从0开始保存,但是这样就要注意后面的比较操作时,i就不是小于mid了,而是小于mid-low,j也不是小于high,j是小于high-low
}
int i = low, j = mid + 1, k = low;
//把数组分为前后相同的两端进行比较。i指向前半段,j指向后半段,k指向要保存的位置
for (; i <= mid && j <= high; k++) {//比较
if (temp[i] < temp[j]) a[k] = temp[i++];
else a[k] = temp[j++];
}
while (j <= high)
//若第一个表没检测完,复制
a[k++] = temp[j++];
while (i <= mid)//若第二个表没检测完,复制
a[k++] = temp[i++];
}
/**
* 快速排序算法
*/
public static void sort(int[] a, int low, int high) {
int start = low;
int end = high;
int key = a[low];
while (end > start) {
//从后往前比较
while (end > start && a[end] >= key) //如果没有比关键值小的,比较下一个,直到有比关键值小的交换位置,然后又从前往后比较
end--;
if (a[end] <= key) {
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
//从前往后比较
while (end > start && a[start] <= key)//如果没有比关键值大的,比较下一个,直到有比关键值大的交换位置
start++;
if (a[start] >= key) {
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
//此时第一次循环比较结束,关键值的位置已经确定了。左边的值都比关键值小,右边的值都比关键值大,但是两边的顺序还有可能是不一样的,进行下面的递归调用
}
//递归
if (start > low) sort(a, low, start - 1);//左边序列。第一个索引位置到关键值索引-1
if (end < high) sort(a, end + 1, high);//右边序列。从关键值索引+1到最后一个
}
/**
* 堆排序
*/
//堆排序函数
public static void HeapSort(int[] arr) {
int n = arr.length - 1;
for (int i = (n - 1) / 2; i >= 0; i--) {
//构造大顶堆,从下往上构造
//i为最后一个根节点,n为数组最后一个元素的下标
HeapAdjust(arr, i, n);
}
for (int i = n; i > 0; i--) {
//把最大的数,也就是顶放到最后
//i每次减一,因为要放的位置每次都不是固定的
swap(arr, i);
//再构造大顶堆
HeapAdjust(arr, 0, i - 1);
}
}
//构造大顶堆函数,parent为父节点,length为数组最后一个元素的下标
public static void HeapAdjust(int[] arr, int parent, int length) {
//定义临时变量存储父节点中的数据,防止被覆盖
int temp = arr[parent];
//2*parent+1是其左孩子节点
for (int i = parent * 2 + 1; i <= length; i = i * 2 + 1) {
//如果左孩子大于右孩子,就让i指向右孩子
if (i < length && arr[i] < arr[i + 1]) {
i++;
}
//如果父节点大于或者等于较大的孩子,那就退出循环
if (temp >= arr[i]) {
break;
}
//如果父节点小于孩子节点,那就把孩子节点放到父节点上
arr[parent] = arr[i];
//把孩子节点的下标赋值给parent
//让其继续循环以保证大根堆构造正确
parent = i;
}
//将刚刚的父节点中的数据赋值给新位置
arr[parent] = temp;
}
//定义swap函数
//功能:将跟元素与最后位置的元素交换
//注意这里的最后是相对最后,是在变化的
public static void swap(int[] arr, int i) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
}
/**
* 基数排序
*
*/
private static void radixSort(int[] array,int d)
{
int n=1;//代表位数对应的数:1,10,100...
int k=0;//保存每一位排序后的结果用于下一位的排序输入
int length=array.length;
int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果,这一位上排序结果相同的数字放在同一个桶里
int[] order=new int[length];//用于保存每个桶里有多少个数字
while(n<d)
{
for(int num:array) //将数组array里的每个数字放在相应的桶里
{
int digit=(num/n)%10;
bucket[digit][order[digit]]=num;
order[digit]++;
}
for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
{
if(order[i]!=0)//这个桶里有数据,从上到下遍历这个桶并将数据保存到原数组中
{
for(int j=0;j<order[i];j++)
{
array[k]=bucket[i][j];
k++;
}
}
order[i]=0;//将桶里计数器置0,用于下一次位排序
}
n*=10;
k=0;//将k置0,用于下一轮保存位排序结果
}
}
}

评论列表( 0 )

你可以在登录后,发表评论

搜索帮助