java实现八大排序
package com.demo01;
import java.util.Arrays;
import java.util.Scanner;
public class Array {
/*
* 冒泡排序冒泡排序:
* 比较相邻的元素。两两对比，如果第一个比第二个数大，就交换位置
* 走第一轮会得到一个最大值/最小值。
* n个数，排好序需要n轮
*/
public static void sortBubbling(int[] arr){
for(int i=0; i<arr.length; i++){
for(int j =i ;j<arr.length; j++){
if(arr[i] > arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.print("排序后的数组：");
for(int i=0; i<arr.length;i++){
System.out.print(arr[i]+",");
}
}
/*
* 快速排序：
* 通过一趟排序将待排序记录分割成独立的两部分，
* 其中一部分记录的关键字均比另一部分关键字小，
* 则分别对这两部分继续进行排序，直到整个序列有序
* 把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，
* 如果比它小交换，比它大不做任何处理；
* 交换了以后再和小的那端比，比它小不交换，比他大交换。
* 这样循环往复，一趟排序完成，左边就是比中轴小的，
* 右边就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。
*/
public static int getMiddle(int[] numbers, int low,int high){
int temp = numbers[low]; //数组的第一个作为中轴
while(low < high){
while(low < high && numbers[high] >= temp){
high--;
}
numbers[low] = numbers[high];//比中轴小的记录移到低端
while(low < high && numbers[low] < temp){
low++;
}
numbers[high] = numbers[low] ; //比中轴大的记录移到高端
}
numbers[low] = temp ; //中轴记录到尾
return low ; // 返回中轴的位置
}
public static void quickSort(int[] numbers,int low,int high){
if(low < high){
int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
quickSort(numbers, low, middle-1); //对低字段表进行递归排序
quickSort(numbers, middle+1, high); //对高字段表进行递归排序
}
}
public static void quick(int[] numbers){
if(numbers.length > 0){ //查看数组是否为空
quickSort(numbers, 0, numbers.length-1);
}
}
/*
* 选择排序:
* 在一组数中，选出最小的一个数与第一个位置交换。
* 在剩下的数中重复上一步
*/
public static void selectSort(int[] numbers){
int size = numbers.length; //数组长度
int temp = 0 ; //中间变量
for(int i = 0 ; i < size ; i++){
int k = i; //待确定的位置
//选择出应该在第i个位置的数
for(int j = size -1 ; j > i ; j--){
if(numbers[j] < numbers[k]){
k = j;
}
}
//交换两个数
temp = numbers[i];
numbers[i] = numbers[k];
numbers[k] = temp;
}
}
/*
* 插入排序：
* 一组数，按其顺序码大小插入到前面已经排序的字序列的合适位置
* （从后向前找到合适位置后），直到全部插入排序完为止。
* 时间复杂度：O（n^2）.
*/
public static void insertSort(int[] numbers){
int size = numbers.length;
int temp = 0 ;
int j = 0;
for(int i = 0 ; i < size ; i++){
temp = numbers[i];
//假如temp比前面的值小，则将前面的值后移
for(j = i ; j > 0 && temp < numbers[j-1] ; j --){
numbers[j] = numbers[j-1];
}
numbers[j] = temp;
}
}
/*
* 希尔排序：
* 将序列分割成为若干子序列分别进行直接插入排序，
* 待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
* 拿数组5, 2, 8, 9, 1, 3，4来说，数组长度为7，当increment为7/2=3时，数组分为两个序列
* 5，2，8和9，1，3，4，
* 9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较
* 第一次排序后数组为5, 1,3, 9, 2, 8, 4
* 第一次后increment的值变为3/2=1,此时对数组进行插入排序
* O（n^2）.
*/
public static void shellSort(int[] data) {
int j = 0;
int temp = 0;
//每次将步长缩短为原来的一半
for (int increment = data.length / 2; increment > 0; increment /= 2){
for (int i = increment; i < data.length; i++) {
temp = data[i];
for (j = i; j >= increment; j -= increment){
if(temp < data[j - increment]){ //如想从小到大排只需修改这里
data[j] = data[j - increment];
}else{
break;
}
}
data[j] = temp;
}
}
}
/*
* 归并排序：
* 将两个（或两个以上）有序表合并成一个新的有序表，
* 即把待排序序列分为若干个子序列，每个子序列是有序的。
* 然后再把有序子序列合并为整体有序序列。
*/
//归并排序
public static void mergeSort(int[] arr){
int[] temp =new int[arr.length];
internalMergeSort(arr, temp, 0, arr.length-1);
}
private static void internalMergeSort(int[] a, int[] temp, int left, int right){
//当left==right的时，已经不需要再划分了
if (left<right){
int middle = (left+right)/2;
internalMergeSort(a, temp, left, middle); //左子数组
internalMergeSort(a, temp, middle+1, right); //右子数组
mergeSortedArray(a, temp, left, middle, right); //合并两个子数组
}
}
// 合并两个有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]。temp是辅助数组。
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
int i=left;
int j=middle+1;
int k=0;
while ( i<=middle && j<=right){
if (arr[i] <=arr[j]){
temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
}
}
while (i <=middle){
temp[k++] = arr[i++];
}
while ( j<=right){
temp[k++] = arr[j++];
}
//把数据复制回原数组
for (i=0; i<k; ++i){
arr[left+i] = temp[i];
}
}
/*
* 堆排序：
* 根节点为最大值，大顶堆
*/
//对data数组从0到lastIndex建大顶堆
public static void buildMaxHeap(int[] data, int lastIndex){
//从lastIndex处节点（最后一个节点）的父节点开始
for(int i=(lastIndex-1)/2;i>=0;i--){
//k保存正在判断的节点
int k=i;
//如果当前k节点的子节点存在
while(k*2+1<=lastIndex){
//k节点的左子节点的索引
int biggerIndex=2*k+1;
//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
if(biggerIndex<lastIndex){
//若果右子节点的值较大
if(data[biggerIndex]<data[biggerIndex+1]){
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其较大的子节点的值
if(data[k]<data[biggerIndex]){
//交换他们
swap(data,k,biggerIndex);
//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
k=biggerIndex;
}else{
break;
}
}
}
}
//交换
private static void swap(int[] data, int i, int j) {
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int [] arr = {54,75,13,678,23,74,1,67,75,12};
/*for(int i=0; i<arr.length;i++){
System.out.println("请输入第"+i+"个数：");
arr[i] = sc.nextInt();
}*/
// sortBubbling(arr);
// selectSort(arr);
// quick(arr);
// insertSort(arr);
// shellSort(arr);
// mergeSort(arr);
int arrayLength=arr.length;
//循环建堆
for(int i=0;i<arrayLength-1;i++){
//建堆
buildMaxHeap(arr,arrayLength-1-i);
//交换堆顶和最后一个元素
swap(arr,0,arrayLength-1-i);
System.out.println(Arrays.toString(arr));
}
printArr(arr);
}
public static void printArr(int[] numbers){
System.out.print("排序后：");
for(int i = 0 ; i < numbers.length ; i ++ ){
System.out.print(numbers[i] + ",");
}
System.out.println("");
}
}
