经典排序算法JAVA实现
import java.util.ArrayList;
import java.util.List;
//经典排序算法JAVA实现
/*排序
* 1.内部排序：只使用内存
* （1）插入排序
* a.直接插入排序
* b.希尔排序
* （2）选择排序
* a.简单选择排序
* b.堆排序
* （3）交换排序
* a.冒泡排序
* b.快速排序
* （4）归并排序
* （5）基数排序
* 2.外部排序：内存和外存结合使用
* */
public class ClassicSortAlgorithm {
public static void main(String[] args){
int[] data = {49 , 38, 65 , 97 , 76 , 13 , 27 , 49 , 78 , 34};
print(data);
// directInsertSort(data);
// shellSort(data);
// simpleSelectSort(data);
// heapSort(data);
// bubbleSort(data);
// quickSort(data);
// mergeSort(data);
radixSort(data);
print(data);
}
/**
* 基数排序
* 算法思想：借助“分配”和“收集”两种操作对单逻辑关键字进行排序
* */
private static void radixSort(int[] data){
int length = data.length;
//寻找最大的数组元素，判断它的位数，可以计算出排序趟数
int max = data[0];
for(int i = 1 ; i < length ; i++){
if(data[i] > max) {
max = data[i];
}
}
//统计最大数的位数
int count = 0;
while(max != 0){
count++;
max /= 10;
}
//建立一个队列保存10个队列，这十个队列分别保存某位 0~9 的数组元素
List<ArrayList<Integer>> queue_total = new ArrayList<ArrayList<Integer>>();
for(int i = 0 ; i < 10 ; i++){
ArrayList<Integer> queue = new ArrayList<Integer>();
queue_total.add(queue);
}
//最大数的位数count，进行count次分配和收集
for(int i = 0 ; i < count ; i++){
//分配数组元素
for(int j = 0 ; j < length ; j++){
//得到数字的第 i+1 位数，从个位开始
//Math.pow(x,y)这个函数是求x的y次方
//i=0个位
//i=1十位
//i=2百位
//.....
int key = data[j] % (int)Math.pow(10, i + 1);
key /= (int)Math.pow(10, i);
//queue_temp保存queue_total中关键字为key的队列
ArrayList<Integer> queue_temp1 = queue_total.get(key);
queue_temp1.add(data[j]);
//使用更新后的队列替换原始队列
queue_total.set(key, queue_temp1);
}
int index = 0;//元素计数器
//收集队列元素
for(int k = 0 ; k < 10 ; k++){
while(queue_total.get(k).size() > 0){
ArrayList<Integer> queue_temp2 = queue_total.get(k);
data[index] = queue_temp2.get(0);
queue_temp2.remove(0);
index++;
}
}
}
}
/**
* 归并排序
* 算法思想：将两个或两个以上的有序表组合成一个新的有序表
* 即把待排序序列分成若干个子序列，每个序列是有序的，然后再把有序子序列合并为整体有序序列
* */
private static void mergeSort(int[] data){
int length = data.length;
mergeSortRealize(data , 0 , length - 1);
}
/**
* 归并排序，不断递归
* */
private static void mergeSortRealize(int[] data, int left, int right) {
//left=right表示数组序列中只有一个数组元素
//left<right最终递归成每组只有两个元素进行归并
if(left < right){
//找到中间元素的下标
//将data平分为data[left...mid]和data[mid+1...right]
int mid = (left + right) / 2;
//对左边数组进行递归，归并为有序序列
mergeSortRealize(data , left , mid);
//对右边数组进行递归，归并为有序序列
mergeSortRealize(data, mid + 1, right);
//合并实现
mergeRealize(data , left , mid , right);
}
}
/**
* 归并排序，实现合并功能
* 核心操作：将一维数组中前后相邻的两个有序序列归并为一个有序序列
* 即将data[left...mid]和data[mid+1...right]合并为一个有序序列
* */
private static void mergeRealize(int[] data, int left, int mid, int right) {
int length = data.length;
//中间数组保存排序好的部分数组元素值
int[] tmp_data = new int[length];
int index = left;//记录tmp_data插入元素的下标
int i = left;//左边数组的下标起始索引
int j = mid + 1;//右边数组的下标起始索引
for( ; i <= mid && j <= right ; ){
//按照从小到大的顺序插入到中间数组
if(data[i] <= data[j]) {
tmp_data[index++] = data[i++];
}else{
tmp_data[index++] = data[j++];
}
}
//如果左边数组元素没有遍历完，将剩余的元素直接复制到中间数组
while(i <= mid){
tmp_data[index++] = data[i++];
}
while(j <= right){
tmp_data[index++] = data[j++];
}
//将中间数组的值重新赋值给data数组
for(i = left ; i <= right ; i++){
data[i] = tmp_data[i];
}
}
/**
* 快速排序
* 算法思想：任意选择一个元素作为枢轴，通过一趟排序将待排记录分割成两部分
* 一部分比枢轴元素小，一部分比枢轴元素大
* 此时枢轴元素在其排好序的正确位置
* 然后用同样的方法递归地排序划分的两部分
* */
private static void quickSort(int[] data){
int length = data.length;
if(length > 0){
quickSortRealize(data , 0 , length - 1);
}
}
/**
* 快速排序，不断递归
* */
private static void quickSortRealize(int[] data , int low , int high){
if(low < high){
int mid = getMiddleIndex(data, low, high);
//对小于枢轴的数组元素进行递归快排
quickSortRealize(data, low, mid - 1);
//对大于枢轴的数组元素进行递归快排
quickSortRealize(data, mid + 1, high);
}
}
/**
* 找枢轴的实际位置
* 算法实现：
*（1） 首先从high所指位置起向前搜索找到第一个关键字小于pivotKey的记录和枢轴记录交换
*（2）然后从low所指位置起向后搜索找到第一个关键字大于pivotKey的记录和枢轴记录交换
*（3）重复上面两步直到low = high
* @param low 保存从前往后遍历的记录下标
* @param high 保存从后往前遍历的记录下标
* */
private static int getMiddleIndex(int[] data , int low , int high){
//将数组中第一个元素作为枢轴
int pivotKey = data[low];
//当low=high时终止循环
while(low < high){
//注意加等号，相等的时候不交换，继续寻找
//从high所指位置起向前搜索找到第一个关键字小于pivotKey的记录下标
while(low < high && data[high] >= pivotKey){
high--;
}
//比枢轴小的记录移到低端
data[low] = data[high];
//从low所指位置起向后搜索找到第一个关键字大于pivotKey的记录下标
while(low < high && data[low] <= pivotKey){
low++;
}
//比枢轴大的记录移到高端
data[high] = data[low];
}
//将枢轴元素放在最终的位置上
data[low] = pivotKey;
//此时low = high
return low;
}
/**
* 冒泡排序
* 算法思想：在要排序的一组数中，对相邻的两个数依次进行比较和调整
* 让较大的数往下沉，较小的数往上冒，每一次循环确定末尾的一个位置数据
* */
private static void bubbleSort(int[] data){
int length = data.length;
//i表示循环次数
for(int i = 0 ; i < length - 1 ; i++){
//每次循环确定数组末尾一个数据，下次循环数组长度减1
for(int j = 0 ; j < length - 1 - i ; j++){
//按照从小到大的顺序
if(data[j] > data[j + 1]){
swap(data, j, j + 1);
}
// //按照从大到小的顺序
// if(data[j] < data[j + 1]){
// swap(data, j, j + 1);
// }
}
}
}
/**
* 堆排序
* 算法思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进
* （1）建堆：初始时把要排序的数的序列看作是一颗顺序存储的二叉树，
* 调整它们存储序使之成为一个堆
* （2）交换：将根节点与堆的最后一个节点交换。
* 然后对前面（n-1）个数重新调整使之成为堆
* 直到只有两个节点的堆，并对它们作交换，得到n个节点的有序序列
* */
private static void heapSort(int[] data){
int length = data.length;
//建堆然后排序，只需做length-1次排序，选出较大（较小）的length-1个关键字
//length-1个位置确定了，整个数组的顺序也就确定了
for(int i = 0 ; i < length - 1 ; i++){
//重新建堆
//第一次确定length-1位置的数字，后面逐步确定length-1-i位置的数字，确定length-1次之后完成排序
//从小到大排列
// buildMaxHeap(data , length - 1 - i);、
//从大到小排列
buildMinHeap(data, length - 1 - i);
//交换堆顶和最后一个无序的元素
swap(data , 0 , length - 1 - i);
}
}
/**
* 建堆，小根堆，交换以后获得的是从大到小的数组
* @param lastIndex最后一个节点的下标
* */
private static void buildMinHeap(int[] data, int lastIndex){
for(int i = (lastIndex - 1) / 2 ; i >= 0 ; i--){
int index = i;
while(index * 2 + 1 <= lastIndex){
int smallerIndex = index * 2 + 1;
if(smallerIndex < lastIndex){
if(data[smallerIndex] > data[smallerIndex + 1]){
smallerIndex++;
}
}
if(data[index] > data[smallerIndex]){
swap(data, index, smallerIndex);
index = smallerIndex;
}else{
//一旦当前节点的值大于或者等于孩子节点的值，不用进行下一层比较直接跳出
break;
}
}
}
}
/**
* 建堆，大根堆，交换以后获得的是从小到大的数组
* @param lastIndex最后一个节点的下标
* */
private static void buildMaxHeap(int[] data, int lastIndex) {
/*基本概念
* 二叉树性质：节点从1开始编号 1 ，2，3，4，5
* 1
* 2 3
* 4 5 6
* 1.如果2i>n，则节点i无左孩子，否则左孩子的节点2i，若2i = n，证明有左孩子，当前节点编号 i = n/2
* 2.如果2i+1>n，则节点i无右孩子，否则右孩子的节点为2i+1，若2i+1=n，证明有右孩子，当前节点编号 i = (n-1)/2
* 3.如果i=1，则节点i是二叉树的根，无双亲；
* 如果i>1，双亲节点是 i/2向下取整 ,节点编号为n
* */
//从lastIndex处节点的父节点开始
//最后一个非终端节点是第 (lastIndex-1)/2向下取整 个节点
//如果lastIndex为奇数 5 左孩子(2i+1) （5-1）/ 2 = 2
//如果lastIndex为偶数 6 右孩子(2i) （6-1）/ 2 = 2
for(int i = (lastIndex - 1) / 2 ; i >= 0 ; i--){
int index = i;//保存正在判断的节点下标
//比较的思想是从当前节点自上而下逐层比较
//（1）如果左右孩子均存在，记录较大值（2）将孩子节点的较大值和当前节点比较，如果大于则交换
//非终端节点至少存在左孩子
while(index * 2 + 1 <= lastIndex){
//暂存较大节点值的下标
int biggerIndex = 2 * index + 1;
//如果biggerIndex<lastIndex说明右孩子也存在
//biggerIndex+1代表index的右孩子节点的下标
if(biggerIndex < lastIndex){
//如果右孩子节点的值较大
if(data[biggerIndex] < data[biggerIndex + 1]){
biggerIndex++;//总是记录较大值的节点标号
}
}
//如果当前节点的值小于左右孩子节点中的较大值，和这个较大值交换
if(data[index] < data[biggerIndex]){
//交换它们
swap(data , index , biggerIndex);
//更新下标
//重新保证index节点的值大于其左右子节点的值
index = biggerIndex;//继续进行下一层的比较
}else{
break;//跳出while循环，进行下一次for循环
}
}
}
}
/**
* 交换数组中的两个元素
* */
private static void swap(int[] data , int i , int j){
int temp_data = data[i];
data[i] = data[j];
data[j] = temp_data;
}
/**
* 简单选择排序
* 算法思想：在要排序的这一组数中，选出最小的一个数与第一个位置的数交换,
* 然后在剩下的数当中再找最小的与第二个位置的数交换，
* 如此循环到倒数第二个数和最后一个数比较为止
* */
private static void simpleSelectSort(int[] data){
int length = data.length;
int position = 0;//保存每次最大元素的下标位置
int min_int = 0;//保存最小元素
//有length个位置的数需要确定，所以需要循环length次
for(int i = 0 ; i < length ; i++){
min_int = data[i];//保存最小元素
position = i;//保存最小位置的下标
for(int j = i + 1 ; j < length ; j++){
if(data[j] < min_int){
min_int = data[j];
position = j;
}
}
data[position] = data[i];
data[i] = min_int;
}
}
/**
* 希尔排序（缩小增量排序）
* 算法思想：算法先将要排序的一组数按照某个增量d(n/2,n为要排序数的个数)
* 分成若干组，每组中记录的下标相差d,对每组中全部元素进行直接插入排序
* 然后再用一个较小的增量对它进行分组，在每组中再进行直接插入排序，
* 当增量减小到1时，进行直接插入排序后，排序完成
* */
private static void shellSort(int[] data) {
int length = data.length;
//计算第一次的增量，增量是多少就代表分了多少组
/* floor()通过该函数计算后的返回值是舍去小数点后的数值
* ceil()只要小数点非0，将返回整数部分+1
* */
int d = (int)Math.ceil(length / 2.0);
int temp_data = 0;
while(d >= 1){
//按照间隔d进行分组，组内进行直接插入排序，d是几就分几组
for(int x = 0 ; x < d ; x++){
for(int i = x + d ; i < length ; i += d){
temp_data = data[i];
int j = i - d;
for(; j >= 0 && temp_data < data[j] ; j -= d){
data[j + d] = data[j];
}
data[j + d] = temp_data;
}
}
// print(data);//打印每次排序的中间结果
d--;//更新d，下一次间隔减一
}
}
/**
* 直接插入排序
* 算法思想：在要排序的一组数中，假设前面（n-1）[n>=2]个数已经排好顺序，
* 现在要把第n个数插入到前面的有序数中，使得这n个数也是排好顺序的，
* 如此反复循环，直到全部排好顺序
* @param data要排序的数组
* */
private static void directInsertSort(int[] data){
int temp_data = 0;
int length = data.length;
//i从1开始，只有一个数组元素的时候默认是有序的
//i代表总共需要插入的次数，1~length-1，也就是进行n-1次插入操作
for(int i = 1 ; i < length ; i++){
temp_data = data[i];//保存每次要插入到有序表的数组元素
//寻找插入位置，从当前有序表的最后一个元素开始比较，找到第一个小于或者等于它的数组元素
//插入到这个元素后面
int j = i - 1 ;
for(; j >= 0 && temp_data < data[j] ; j--){
data[j + 1] = data[j];//将大于temp_data的值整体后移一个单位
}
//找到第一个小于或者等于它的数组元素下标为j,则插入的位置为j+1
data[j + 1] = temp_data;
}
}
/**
* 数组打印
* */
public static void print(int[] data){
int length = data.length;
for(int i = 0 ; i < length ; i++){
System.out.print(data[i] + " ");
}
System.out.println();
}
}