简单选择排序、冒泡排序、插入排序、希尔排序、堆排序、快速排序、归并排序、基数排序
import java.util.Arrays;
public class Sort {
public static void main(String[] args) {
int[] a = {58,51,75,94,11,96,12,35,17,95,28,15,81}; //
int[] b = {1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,16};
quickSort(a, 0 , a.length-1);
quickSort(b, 0 , b.length-1);
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(b));
}
/**
* 希尔排序
*
* 时间复杂度最坏n平方， 空间复杂度1， 不稳定
*
*/
public static void shellSort(int[] array) {
int n = array.length;
// 希尔序列，从待排元素的个数除以2为初始值，每次循环一次，数值就除以2
for(int i = n/2 ; i>=1; i=i/2) {
// 调用插入排序
// 注意！ 待排元素并非连续，下标间隔是希尔序列的值
for(int j=i; j<n ; j++) {
int m=j;
int temp = array[m];
for( ; m>=i && array[m]<array[m-i] ; m = m-i) {
array[m] = array[m-i];
}
array[m-i] = temp;
}
}
}
/**
* 插入排序
* @param array
*
* 时间复杂度 n平方，空间复杂度1，稳定
* 如果序列基本有序，用插入排序效率更高
*/
public static void insertSort(int[] array) {
for(int i=1; i<array.length ; i++) {
// 将for循环的初始值在外面定义，以便确定待插入元素需要插入的位置
int j = i;
// 记录待插入元素
int temp = array[j];
// 将待插入元素与已经排好序的元素比较（从后往前比），若待插入元素较小，则待排元素往后挪一位
for( ; j>0 && temp < array[j-1] ; j--) {
array[j] = array[j-1];
}
// for循环终止时，j的值就是待插入元素需要插入的位置。
array[j] = temp;
}
}
/**
* 冒泡排序
* @param array
*
* 时间复杂度 n平方，空间复杂度1，稳定
*/
public static void bubbleSort(int[] array) {
for(int i=array.length-1; i>0 ; i--) {
// 如果一趟循环下来，没有交换元素，说明已经有序，可以直接跳出最外层循环
boolean hasSorted = true;
for(int j=0; j<i ; j++) {
// 若第j个元素比第j+1个元素大，则交换位置
// 一趟for循环后，最大的元素就放在了最后一个位置
// 所以每经历一次for循环，下一次循环时就可以少检查一个元素（最后的元素）
// 这也是为什么最外层的for循环从array.length-1开始，而不是从0开始的原因。
if(array[j]>array[j+1]) {
hasSorted = false;
int temp = array[j+1] ;
array[j+1] = array[j];
array[j] = temp;
}
}
if(hasSorted) {
break;
}
}
}
/**
* 堆排序，是对选择排序的一种改进
*
* 时间复杂度：NlogN 空间复杂度1
*
*/
public static void heap(int[] array ) {
// 将待排数组转为最大堆，（若要得到递增序列，则建立最大堆，要得到递减序列则建立最小堆）
buildMaxHeap(array , (array.length-1)/2 , array.length) ;
// 循环删除根元素（最大值）
// 将根元素与数组最后一个元素互换，最大堆长度减1
// 调整后的堆转换成最大堆，让最大元素放到堆顶部，循环往复，得到非递减序列
for(int i=array.length-1; i>0 ; i--) {
int temp = array[i];
array[i] = array[0];
array[0] = temp;
buildMaxHeap(array , 0 , i) ;
}
}
/**
* 建立最大堆（将指定数组转化为最大堆）
* @param array 待排数组
* @param root 根节点
* @param n 待排元素个数
*/
public static void buildMaxHeap(int[] array , int root , int n) {
// 若果没有左右子树，则已经是最大堆，立即返回
if(root>=n) {
return;
}
for(int i = root ; i>=0 ; i--) {
int left = 2*i+1;
int right = 2*i+2;
//既有左子树又有右子树
if( left < n && right < n ) {
// 找出左、右子树和根节点比较，将三者的最大值调整到根节点
int big = array[left]>array[right]?left:right;
if(array[big] > array[i]) {
int temp = array[i];
array[i] = array[big];
array[big] = temp;
// 若将根节点与左子树或右子树互换了，要继续将左子树或右子树调整为最大堆
buildMaxHeap(array, big, n);
}
// 只有左子树，没有右子树
}else if(left < n && right >= n) {
if(array[left]>array[i]) {
int temp = array[i];
array[i] = array[left];
array[left] = temp;
buildMaxHeap(array, left, n);
}
}
}
}
/**
* 归并排序——核心是有序子序列的归并
* 分为 递归版本 和 非递归版本
* 稳定，时间复杂度NlogN,空间复杂度N
*/
public static void mergeSort(int[] array) {
//方法一：递归
recursionSort(array , new int[array.length] , 0 , array.length-1);
// 方法二：非递归
mSort(array , new int[array.length] , 0 , array.length-1);
}
/**
* 归并排序————递归算法
* @param array 待排数组
* @param temp 临时数组，注意！！！临时数组不能在本方法内创建，而应该以参数引用方式传递进方法，否则空间复杂度爆炸
* @param left 待排数组的左边界（含）
* @param right 待排数组的右边界（含）
*/
public static void recursionSort(int[] array,int[] temp, int left , int right) {
if(left<right) {
int mid = left + (right-left)/2;
recursionSort(array,temp,left,mid ); // 递归调用左边
recursionSort(array,temp, mid+1, right); // 递归调用右边
// 归并左右两个有序序列
merge(array,temp,left,mid+1,right);
}
}
/**
* 将两个有序子序列进行合并
* @param array 含有两个有序子序列的数组（两个子序列连续）
* @param temp 临时数组
* @param left 第一个有序子序列的左边界
* @param right 第二个有序子序列的左边界
* @param rightEnd 第二个有序子序列的右边界
*/
public static void merge(int[] array, int[] temp , int left , int right , int rightEnd){
int total = rightEnd - left +1 ;
int curIndex = left; // 用于标记在临时数组中应该存放在哪个位置
int leftEnd = right-1; // 第一个有序序列的右边界
while(left<=leftEnd && right <= rightEnd) {
if(array[left] < array[right]) {
temp[curIndex] = array[left];
left++;
curIndex++;
}else {
temp[curIndex] = array[right];
right++;
curIndex++;
}
}
//情况一：第二个序列已经归并完毕，第一个序列还有待归并元素
while(left<=leftEnd) {
temp[curIndex] = array[left];
left++;
curIndex++;
}
//情况二：第一个序列已经归并完毕，第二个序列还有待归并元素
while(right<=rightEnd) {
temp[curIndex] = array[right];
right++;
curIndex++;
}
for(int i=0; i<total ; i++) {
array[rightEnd] = temp[rightEnd];
rightEnd--;
}
}
/**
* 归并算法——非递归
* @param array 待排数组
* @param temp 临时数组
* @param left 待排左边边界
* @param right 待排右边边界
*/
public static void mSort(int[] array,int[] temp, int left , int right) {
int step = 1; // 每次归并的有序序列的长度，起始为1，只有每次翻倍
while(step<array.length) {
for(int i=0; i<=right; i=i+2*step) {
int secondBegin = Math.min(i+step, array.length);
// 若最后只有一个有序序列，则第二段有序序列的起始位置比终止位置大，方便merge函数处理
int secondEnd = Math.min(i+2*step-1, array.length-1);
// 将左右两个有序序列进行归并
merge(array,temp,i,secondBegin,secondEnd );
}
step = step*2;
}
}
/**
* 快速排序
*
*/
public static void quickSort(int[] array, int left , int right ) {
System.out.println("left:"+left + " right:"+right);
if(left>=right) {
return;
}
// 首先选取待排元素的头、中、尾三个元素中的中位数，将其作为主元
int mid = left + (right - left)/2;
if(array[left]>array[mid]) {
int temp = array[left];
array[left] = array[mid];
array[mid] = temp;
}
if(array[mid]>array[right]) {
int temp = array[mid];
array[mid] = array[right];
array[right] = temp;
}
if(array[left]>array[mid]) {
int temp = array[left];
array[left] = array[mid];
array[mid] = temp;
}
// 至此，array[mid]已经是中位数了，需要将其放在array[right-1]的位置上。
// 后续排序只需要考虑array[left +1 ] 到 array[right-2];
int temp = array[right-1];
array[right-1] = array[mid];
array[mid] = temp;
// 若待排元素不超过3个，则已经有序，直接退出
if(right-left<=3) {
return;
}
// 将选择的主元一次性放入应该放的位置，保证再后续不需要挪动位置
int i= left+1; // 左指针下标
int j = right-2; // 右指针下标
int mainValue = array[right-1]; // 主元的值
// 当左指针比右指针还大，说明已经遍历完了，需跳出循环
while(i<j) {
// 当左指针发现一个元素比主元大，则跳出循环
while(array[i]<mainValue) {
i++;
}
// 当右指针发现一个元素比主元小，则跳出循环
while(array[j]>mainValue) {
j--;
}
// 若左指针比右指针小，说明左指针碰到比主元大的元素，同时右指针碰到比主元小的元素，这两个元素应该交换位置
if(i<j) {
int temp2 = array[j];
array[j] = array[i];
array[i] = temp2;
}
}
// 跳出while循环后，i的值就是主元应该放置的最终位置。
int temp3 = array[i];
array[i] = mainValue;
array[right-1] = temp3;
// 递归调用主元左边元素
quickSort(array,left,i-1);
// 递归调用主元右边元素
quickSort(array, i+1, right);
}
/**
* 表排序，当元素的移动需要耗费很大资源时使用
* 建立一个下标与元素的对应关系表，对表进行排序
*/
/**
* 桶排序
* 例如将某大学的所有学生的英语成绩进行排序，成绩的可能只有0-100共计101种，这种情况可以为成绩建立
* 101个桶，再将学生成绩依次放入桶中
*/
/**
* 基数排序
* 在桶排序的基础上继续演进
* 若要对0-999的数字进行排序，待排元素比桶的个数要小的多，则适用基数排序
*
* 基数排序的次位有限原则方法——先对个位数（比较的时候优先级最低的）建桶，将待排元素依次放到对应桶中
* 再为十位数建桶，从小到大遍历个位数的桶，将元素放到十位数的桶中.
* 最后为百位数建桶，从小到大遍历十位数的桶，将元素放到百位数的桶中
* 最后从小到大遍历百位数的桶，依次输出元素。
*
*
*/
}