import java.util.Arrays;
import java.util.Random;
import java.util.ArrayList;
/**
* 默认升序排列
* 可以调用reverse(int[] arr)方法反转数组使之逆序
* 暂时没写完，学会一样就更新一样
*/
public class Sorts{
private static Random rand = new Random();
public static void main(String[] args){
int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
straightInsertSort(a);
System.out.println(Arrays.toString(a));
int[] b = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
radixSort(b);
System.out.println(Arrays.toString(b));
}
/**
* 反转数组
* @param arr 待反转数组
*/
public static void reverse(int[] arr){
for(int i = 0; i < arr.length/2; i++){
swap(arr, i, arr.length-1-i);
}
}
/**
* 交换数组元素
* @param arr 待交换的数组
* @param i 位置1
* @param j 位置2
*/
private static void swap(int[] arr, int i , int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* ---------------------直接插入排序---------------------
* 在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，
* 现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。
* 如此反复循环，直到全部排好顺序。
* @param arr 待排序数组
*/
public static void straightInsertSort(int[] arr){
if(arr.length < 2) return;
for(int i = 1; i < arr.length; i++){ //i左侧都已排序
int temp = arr[i]; //a[i]会变成其他值，故先转移到临时变量
int j = i -1;
while(j >= 0 && temp < arr[j]){ // j+1最大值为arr.length-1，故不会越界
arr[j+1] = arr[j--];
}
arr[j+1] = temp;
}
}
/**
* ---------------------希尔排序（最小增量排序）---------------------
* 基本思想：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组
* 每组中记录的下标相差d.对每组中全部元素进行直接插入排序
* 然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。
* 当增量减到1时，进行直接插入排序后，排序完成。
* @param arr 待排序数组
*/
public static void shellSort(int[] arr){
int d = arr.length;
if (d < 2) return; //不符合条件则退出方法
while(d > 1){
d = (d-1)/3; //网上看到的，据说d = 3d + 1是最快的排序序列
for(int i = 0; i < d; i++){ //一共拆成d个数组
for(int j = i+d; j < arr.length; j += d){ //对每个数组进行插入排序
int temp = arr[j];
int k = j-d;
while(k >= 0 && temp < arr[k]){
arr[k+d] = arr[k];
k -= d;
}
arr[k+d] = temp;
}
}
}
}
/**
* ---------------------直接选择排序---------------------
* 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
* 然后在剩下的数当中再找最小的与第二个位置的数交换
* 如此循环到倒数第二个数和最后一个数比较为止。
* @param arr [description]
*/
public static void straightSelectSort(int[] arr){
if (arr.length < 2) return; //不符合条件则退出。
int start = 0; //起始索引
int i = 1; //遍历用的索引
int min; //最小数的索引
for(int j = 0; j <= arr.length-2; j++){
min = j;
for(int k = j; k < arr.length; k++){
if (arr[k] < arr[min]) min = k;
}
if (min != j) swap(arr, min, j);
}
}
/**
* ---------------------堆排序---------------------
* 堆的定义如下：具有n个元素的序列（h1,h2,…,hn),
* 当且仅当满足（h(i) >= h(2i), h(i) >= h(2i+1) ）
* 或（h(i) <= h(2i), h(i) <= h(2i+1)） (i=1,2,…,n/2)时称之为堆。
* 在这里只讨论满足前者条件的堆。
* 由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。
* 完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
* 初始时把要排序的数的序列看作是一棵顺序存储的二叉树，
* 调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。
* 然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。
* 依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。
* 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。
* 所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
* @param arr [description]
*/
public static void heapSort(int[] arr){
}
/**
* ---------------------冒泡排序---------------------
* 在要排序的一组数中，对当前还未排好序的范围内的全部数，
* 自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。
* 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
* @param arr 要排序的数组
*/
public static void bubbleSort(int[] arr){
if (arr.length < 2) return;
for(int i = 0; i < arr.length; i++){
for(int j = 0; j <= arr.length-2-i; j++){
if (arr[j] > arr[j+1]) swap(arr, j, j+1);
}
}
}
/**
* ---------------------快速排序---------------------
* 首先在要排序的序列中选取一个中轴值，而后将序列分成三个部分，
* 其中左边部分中的元素均小于中轴值，中间部分元素均等于中轴值，
* 右边的部分的元素均大于中轴值，
* 而后通过递归调用快速排序的过程分别对左右两个部分进行排序，
* 最后将三部分结果合并即可得到最后的排序序列。
* @param arr 待排序的数组
*/
public static void quickSort(int[] arr){ //快速排序入口，调用时不必填三个参数
quickSort(arr, 0, arr.length-1);
}
/**
* 快速排序执行部分
* @param arr 待排序数组
* @param start 开始索引
* @param end 结束索引
*/
private static void quickSort(int[] arr, int start, int end){
if (start >= end) return;
int index = arr[start + rand.nextInt(end-start+1)]; //中轴值
int left = start, right = end; //指示左右两端未排序的边界索引
int i = start; // 用于排序
while(i <= right){
if (arr[i] < index){ //小于中轴值则移到左侧
swap(arr, left++, i++);
}else if (arr[i] > index){ //大于中轴值则移到右侧
swap(arr, right--, i); //当前i位置的值未排序，故i不自增
}else{
i++;
}
}
//排完后left左侧均为小于index的数，right右侧均为大于index的数
quickSort(arr, start, left-1);
quickSort(arr, right+1, end);
}
/**
* ---------------------归并排序---------------------
* 将两个（或两个以上）有序表合并成一个新的有序表，
* 即把待排序序列分为若干个子序列，每个子序列是有序的。
* 然后再把有序子序列合并为整体有序序列。
* @param arr 待排序数组
*/
public static void mergeSort(int[] arr){
mergeSort(arr, 0, arr.length-1);
}
/**
* 归并排序递归部分
* @param arr 待排序数组
* @param start 开头索引
* @param end 末尾索引
*/
private static void mergeSort(int[] arr, int start, int end){
if(start >= end) return; //一个元素则不须排序
int mid = (start + end) / 2;
mergeSort(arr, start, mid); //分别拆开
mergeSort(arr, mid+1, end); //经验证，这样不会数组越界
merge(arr, start, mid, mid+1, end); //归并
}
/**
* 归并排序合并数组
* 其中end1 + 1 = start2，拆成两部分更直观
* @param arr 待合并数组
* @param start1 左半部分开头索引
* @param end1 左半部分末尾索引
* @param start2 右半部分开头索引
* @param end2 右半部分末尾索引
*/
private static void merge(int[] arr, int start1, int end1, int start2, int end2){
int[] tmp = new int[end1-start1+end2-start2+2]; //临时存放用的数组
int i = start1, j = start2, k = 0; //分别用于遍历数组
while(i <= end1 && j <= end2){ //归并排序
tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; //若相等，则按原来的次序，优先放arr[i]
}
//再把剩余的数组内容存入tmp[]，上一步已经排尽的数组，其i或j的值是大于下界的
while(i <= end1){
tmp[k++] = arr[i++];
}
while(j <= end2){
tmp[k++] = arr[j++];
}
// 最后把tmp复制回原数组
System.arraycopy(tmp, 0, arr, start1, tmp.length);
}
/**
* 基数排序
* 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
* 然后，从最低位开始，依次进行一次排序。
* 这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
* @param arr 待排序数组
*/
public static void radixSort(int[] arr){
//创建Integer数组，使中间步骤不必频繁转换类型
Integer[] array = new Integer[arr.length];
for(int i = 0; i < arr.length; i++){
array[i] = arr[i];
}
//创建链表用于保存同位数的数字，无法创建泛型数组，只能用这种方式
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < 10; i++){
ArrayList<Integer> tmp = new ArrayList<Integer>();
list.add(tmp);
}
//先找出最大位数，即最大值的位数
int max = arr[0];
for(int i = 1; i < arr.length; i++){
if (max < arr[i]){
max = arr[i];
}
}
int place = String.valueOf(max).length(); //最大值的位数
int dividend = 1; //除数，用于置某位为个位
//开始排序
for(int i = 1; i <= place; i++){
for(Integer num : array){ //数组根据相应位数存入list
list.get(num / dividend % 10).add(num);
}
//取出数字放回数组
int index = 0;
for(ArrayList<Integer> tmp : list){
while(tmp.size() > 0){
array[index++] = tmp.get(0);
tmp.remove(0);
}
}
dividend *= 10; //进位
}
//把最终结果存回arr
for(int i = 0; i < arr.length; i++){
arr[i] = array[i];
}
}
}
版权声明：本文为博主原创文章，未经博主允许不得转载。