题目内容：
 
输入
 
N组数据
 
名字+成绩
 
输出：按照成绩升序或降序排列，若成绩相同，按照录入的先后顺序
 
import java.util.Scanner;
 
public class Score {
 
private static String[] names;
 
private static int[] grades;
 
private static boolean compare(int i, int j, int flag){
 
return flag == 0 ? grades[i] > grades[j] : grades[i] < grades[j];
 
}
 
private static void exch(int i, int j){
 
String tempS = names[j];
 
int tempG = grades[j];
 
names[j] = names[i];
 
grades[j] = grades[i];
 
names[i] = tempS;
 
grades[i] = tempG;
 
}
 
public static void sort(int flag){
 
for(int i = 1; i < names.length; i++)
 
for(int j = i; j > 0 && compare(j,j - 1,flag); j--){
 
exch(j,j - 1);
 
}
 
}
 
public static void main(String[] args) {
 
// TODO Auto-generated method stub
 
Scanner input = new Scanner(System.in);
 
while(input.hasNext()){
 
int n = input.nextInt();//人数
 
int flag = input.nextInt();
 
names = new String[n];
 
grades = new int[n];
 
for(int i = 0; i < n; i++){
 
names[i] = input.next();
 
grades[i] = input.nextInt();
 
}
 
sort(flag);
 
for(int i = 0; i < n; i++){
 
System.out.println(names[i] + " " + grades[i]);
 
}
 
}
 
}
 
}
 
标签：成绩,java,int,flag,grades,static,names,input,排序
 
来源： https://blog.51cto.com/14232658/2455131

 
算法总结:
 

 
参数说明:
 
稳定性:相同数组中变量a与b如果值相等排序时,a原本在b前面,出现a在b后面的现象。
 
时间复杂度： 一个算法执行所耗费的时间。
 
空间复杂度：运行完一个程序(函数)所需内存的大小。
 
n: 数据规模(数组数据个数)
 
k: “桶”的个数
 
In-place(内排序): 占用常数内存，不占用额外内存(所有排序操作都在内存中完成)
 
Out-place(外排序): 占用额外内存(由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行)
 
排序算法案例:
 
①冒泡排序
 
本质:通过for循环 利用两两比较的方式依次找到相对大值放在右边,实现每次循环后,将未排序的数组部分最大值放在右边
 

 
代码说明:
 
public static void sort(int[] arr) {//外层循环控制比较的次数 arr[arr.leng-1]后面没有比较的数据 比较数[0,arr.leng-1-1]
 
for (int i = 0; i < arr.length-1; i++){//内层循环控制到达位置 被比较数据[1,arr.leng-1-i(已经比较过的次数)]
 
for (int j = 1; j < arr.length - 1 - i; j++){if (arr[j ] 
 
arr[j]=arr[j];
 
arr[j]=temp;
 
}
 
}
 
}
 
}
 
②选择排序
 
本质:每次循环,找到该次循环的最小值,记录索引排序
 

 
代码说明:
 
public static void sort(int[] array) {//外层循环控制循环次数
 
for (int i = 0; i < array.length; i++) {int minIndex =i;//内层循环 找到循环时的最小值得索引
 
for (int j = i; j < array.length; j++) {if (array[j] < array[minIndex]) //找到最小的数
 
minIndex = j; //将最小数的索引保存
 
}int temp =array[minIndex];
 
array[minIndex]=array[i];
 
array[i]=temp;
 
}
 
}
 
③插入排序:
 
本质:通过循环依次从右到左依次判断,进入插入对应位置,已形成循环次数对应索引左边的有序与右边的无序数据
 

 
代码说明:
 
public static void sort(int[] array) {intcurrent;//外层循环控制循环次数
 
for (int i = 0; i < array.length - 1; i++) {
 
current= array[i + 1];int preIndex =i;//内层循环控制索引数据右移或插入
 
while (preIndex >= 0 && current 
 
array[preIndex+ 1] =array[preIndex];
 
preIndex--;
 
}
 
array[preIndex+ 1] =current;
 
}
 
}
 
④希尔排序:
 
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
 
具体算法描述：
 
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 
按增量序列个数k，对序列进行k 趟排序；
 
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 

 
代码说明:
 
public static void sort(int[] array) {
 
int len = array.length;
 
int temp, gap = len / 2;
 
while (gap > 0) {
 
for (int i = gap; i < len; i++) {
 
temp = array[i];
 
int preIndex = i - gap;
 
while (preIndex >= 0 && array[preIndex] > temp) {
 
array[preIndex + gap] = array[preIndex];
 
preIndex -= gap;
 
}
 
array[preIndex + gap] = temp;
 
}
 
gap /= 2;
 
}
 
}
 
⑤归并排序
 
算法描述
 
把长度为n的输入序列分成两个长度为n/2的子序列；
 
对这两个子序列分别采用归并排序；
 
将两个排序好的子序列合并成一个最终的排序序列。
 

 
代码说明:   补充:暂时未发布该随笔引用数据参数传递与基本数据参数传递
 
/*** 归并排序 由于归并排序并不是在原有数组进行操作,应该返回新数组地址*/
 
public static int[] MergeSort(int[] array) {if (array.length < 2)returnarray;int mid = array.length / 2;
 
nt[] left= java.util.Arrays.copyOfRange(array, 0, mid);int[] right =java.util.Arrays.copyOfRange(array, mid, array.length);returnmerge(MergeSort(left), MergeSort(right));
 
}/*** 归并排序——将两段排序好的数组结合成一个排序数组*/
 
public static int[] merge(int[] left, int[] right) {int[] result = new int[left.length +right.length];for (int index = 0, i = 0, j = 0; index < result.length; index++) {if (i >=left.length)
 
result[index]= right[j++];else if (j >=right.length)
 
result[index]= left[i++];else if (left[i] >right[j])
 
result[index]= right[j++];elseresult[index]= left[i++];
 
}returnresult;
 
}
 
⑥快速排序(Quick Sort)
 
算法描述:
 
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。
 
从数列中挑出一个元素，称为 “基准”(pivot)；
 
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作；
 
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
 

 
代码说明
 

 
/*** 快速排序方法*/
 
public static int[] QuickSort(int[] array, int start, int end) {
 
if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
 
int smallIndex = partition(array, start, end);
 
if (smallIndex > start)
 
QuickSort(array, start, smallIndex - 1);
 
if (smallIndex < end)
 
QuickSort(array, smallIndex + 1, end);
 
return array;
 
}
 
/*** 快速排序算法——partition*/
 
public static int partition(int[] array, int start, int end) {
 
int pivot = (int) (start + Math.random() * (end - start + 1));
 
int smallIndex = start - 1;
 
swap(array, pivot, end);
 
for (int i = start; i <= end; i++)
 
if (array[i] <= array[end]) {
 
smallIndex++;
 
if (i > smallIndex)
 
swap(array, i, smallIndex);
 
}
 
return smallIndex;
 
}
 
/**交换数组内两个元素*/
 
public static void swap(int[] array, int i, int j) {
 
int temp = array[i];
 
array[i] = array[j];
 
array[j] = temp;
 
}
 

 
⑦堆排序(Heap Sort)
 
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。
 
算法描述
 
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
 
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
 
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
 

 
代码说明
 
注意：这里用到了完全二叉树的部分性质：详情见《数据结构二叉树知识点总结》
 

 
//声明全局变量，用于记录数组array的长度；
 
static int len;
 
/*** 堆排序算法*/
 
public static int[] HeapSort(int[] array) {
 
len = array.length;
 
if (len < 1) return array;
 
//1.构建一个最大堆
 
buildMaxHeap(array);
 
//2.循环将堆首位(最大值)与末位交换，然后在重新调整最大堆
 
while (len > 0) {
 
swap(array, 0, len - 1);
 
len--;
 
adjustHeap(array, 0);
 
}
 
return array;
 
}
 
/**
 
* 建立最大堆
 
*
 
* @param array
 
*/
 
public static void buildMaxHeap(int[] array) {
 
//从最后一个非叶子节点开始向上构造最大堆
 
for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1)
 
adjustHeap(array, i);
 
}
 
}
 
/*** 调整使之成为最大堆*/
 
public static void adjustHeap(int[] array, int i) {
 
int maxIndex = i;
 
//如果有左子树，且左子树大于父节点，则将最大指针指向左子树
 
if (i * 2 < len && array[i * 2] > array[maxIndex])
 
maxIndex = i * 2;
 
//如果有右子树，且右子树大于父节点，则将最大指针指向右子树
 
if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
 
maxIndex = i * 2 + 1;
 
//如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
 
if (maxIndex != i) {
 
swap(array, maxIndex, i);
 
adjustHeap(array, maxIndex);
 
}
 
}
 

 
⑧计数排序(CountingSort)
 
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
 
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
 
算法描述--每个桶只存储单一键值
 
找出待排序的数组中最大和最小的元素；
 
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
 
对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加)；
 
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
 

 
代码实现
 

 
/*** 计数排序 */
 
public static int[] CountingSort(int[] array) {
 
if (array.length == 0) return array;
 
int bias, min = array[0], max = array[0];
 
for (int i = 1; i < array.length; i++) {
 
if (array[i] > max)
 
max = array[i];
 
if (array[i] < min)
 
min = array[i];
 
}
 
bias = 0 - min;
 
int[] bucket = new int[max - min + 1];
 
Arrays.fill(bucket, 0);
 
for (int i = 0; i < array.length; i++) {
 
bucket[array[i] + bias]++;
 
}
 
int index = 0, i = 0;
 
while (index < array.length) {
 
if (bucket[i] != 0) {
 
array[index] = i - bias;
 
bucket[i]--;
 
index++;
 
} else
 
i++;
 
}
 
return array;
 
}
 

 
⑨桶排序(BucketSort)
 
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
 
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排
 
算法描述--每个桶存储一定范围的数值
 
人为设置一个BucketSize，作为每个桶所能放置多少个不同数值(例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3)；
 
遍历输入数据，并且把数据一个一个放到对应的桶里去；
 
对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
 
从不是空的桶里把排好序的数据拼接起来。
 
注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。
 

 
代码说明
 

 
/*** 桶排序*/
 
public static ArrayList BucketSort(ArrayList array, int bucketSize) {
 
if (array == null || array.size() < 2)
 
return array;
 
int max = array.get(0), min = array.get(0);
 
// 找到最大值最小值
 
for (int i = 0; i < array.size(); i++) {
 
if (array.get(i) > max)
 
max = array.get(i);
 
if (array.get(i) < min)
 
min = array.get(i);
 
}
 
int bucketCount = (max - min) / bucketSize + 1;
 
ArrayList> bucketArr = new ArrayList<>(bucketCount);
 
ArrayList resultArr = new ArrayList<>();
 
for (int i = 0; i < bucketCount; i++) {
 
bucketArr.add(new ArrayList());
 
}
 
for (int i = 0; i < array.size(); i++) {
 
bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
 
}
 
for (int i = 0; i < bucketCount; i++) {
 
if (bucketSize == 1) { // 如果带排序数组中有重复数字时
 
for (int j = 0; j < bucketArr.get(i).size(); j++)
 
resultArr.add(bucketArr.get(i).get(j));
 
} else {
 
if (bucketCount == 1)
 
bucketSize--;
 
ArrayList temp = BucketSort(bucketArr.get(i), bucketSize);
 
for (int j = 0; j < temp.size(); j++)
 
resultArr.add(temp.get(j));
 
}
 
}
 
return resultArr;
 
}
 

 
⑩基数排序(RadixSort)
 
基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；
 
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
 
算法描述 --根据键值的每位数字来分配桶
 
取得数组中的最大数，并取得位数；
 
arr为原始数组，从最低位开始取每个位组成radix数组；
 
对radix进行计数排序(利用计数排序适用于小范围数的特点)；
 

 
代码实现
 

 
/*** 基数排序/
 
public static int[] RadixSort(int[] array) {
 
if (array == null || array.length < 2)
 
return array;
 
// 1.先算出最大数的位数；
 
int max = array[0];
 
for (int i = 1; i < array.length; i++) {
 
max = Math.max(max, array[i]);
 
}
 
int maxDigit = 0;
 
while (max != 0) {
 
max /= 10;
 
maxDigit++;
 
}
 
int mod = 10, div = 1;
 
ArrayList> bucketList = new ArrayList>();
 
for (int i = 0; i < 10; i++)
 
bucketList.add(new ArrayList());
 
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
 
for (int j = 0; j < array.length; j++) {
 
int num = (array[j] % mod) / div;
 
bucketList.get(num).add(array[j]);
 
}
 
int index = 0;
 
for (int j = 0; j < bucketList.size(); j++) {
 
for (int k = 0; k < bucketList.get(j).size(); k++)
 
array[index++] = bucketList.get(j).get(k);
 
bucketList.get(j).clear();
 
}
 
}
 
return array;
 
}
 

 
参考链接:

 
排序算法
 
排序算法算是我们学习算法的入门篇，在正式介绍各种排序算法前，先介绍一下要用到的一些术语：稳定排序：如果a本来在b的前面，且a==b，排序以后a依旧在b的前面，那就是稳定排序，否在是非稳定排序
 
原地排序：就是在排序过程中不申请多于的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。而非原地排序就是需要利用额外的数组来辅助排序。
 
总览：
 

 
选择排序
 
代码思路
 
首先找到数组中最小的元素，其次将其与数组中第一个元素交换位置，然后在剩下的数组中找到最小的元素，然后和第二个元素交换，以此类推，直到交换完毕。
 
特点
 
数据移动最少，运行时间与数据输入时的顺序无关
 
复杂度与排序特点时间复杂度：O(n²)
 
空间复杂度：O(1)
 
非稳定排序
 
原地排序
 
使用环境
 
数据量少
 
算法代码// 从小到大
 
private static void sort(int[] nums){
 
int n=nums.length;
 
int minIndex,temp;
 
for(int i=0;i
 
minIndex=i;
 
for(int j=i+1;j
 
if(nums[j]
 
minIndex=j;
 
}
 
}
 
temp=nums[i];
 
nums[i]=nums[minIndex];
 
nums[minIndex]=temp;
 
}
 
}
 
插入排序
 
代码思路
 
像抓牌一样，将牌暂时放入现在的适当的位置。当到最后一个元素时就排序完成了。就像把一个无序数组中的数据整合到一个有序数组中。
 
特点
 
运行时间与输入情况有关，对于一个部分有序(数组中元素离最终位置都不远，或者一个有序的大数组加一个小数组)来说速度比较快
 
复杂度时间复杂度：O(n²)
 
空间复杂度：O(1)
 
稳定排序
 
原地排序
 
使用环境
 
数组基本有序，或者一个有序的大数组中添加一些小数据。
 
算法代码// 从小到大排序
 
private static void sort(int[] nums) {
 
int n=nums.length;
 
int preIndex,current;
 
for(int i=1;i
 
preIndex=i-1;
 
current=nums[i];
 
while (preIndex>=0&&nums[preIndex]>current){
 
nums[preIndex+1]=nums[preIndex];
 
preIndex--;
 
}
 
nums[preIndex+1]=current;
 
}
 
}
 
冒泡排序
 
代码思路
 
十分简单，重复访问，依次比较进行交换，交换过多比较相邻元素，大就交换
 
从第一对开始，到最后一对，一次排序后保证最大的位于末尾
 
重复n次
 
特点
 
思路简单
 
复杂度时间复杂度：O(n2)
 
空间复杂度：O(1)
 
稳定排序
 
原地排序
 
使用环境
 
无适用场景一般用于学习算法。
 
算法代码private static void sort(int[] nums) {
 
int n=nums.length;
 
for(int i=0;i
 
for(int j=0;j
 
if(nums[j]>nums[j+1]){
 
int temp=nums[j];
 
nums[j]=nums[j+1];
 
nums[j+1]=temp;
 
}
 
}
 
}
 
}改良冒泡排序算法
 
在我们遍历的过程中，会发现从开始第一队到最后一对都没有发生交换，此时意味着，剩下这些待排序的元素已经是有序的数据，无序再次排序，所以我们可以引入一个标志，当遇到此情况的时候，直接跳出循环。减少无意义的比较和缩短排序时间。
 
希尔排序(缩小增量排序)
 
代码思路
 
希尔排序是插入排序的一种变种，原来插入排序的优势在于数据基本有序的情况下性能很好，但是如果原数组中的元素距离其正确位置很远的话，效率就不是很高，而希尔排序正是优化了这一点。
 
希尔排序就是为了加快速度简单的改进了插入排序，交换不相邻的元素以对数据的局部进行排序。
 
先使数组中任意间隔为h的元素是有序的。最后对于一个以1结尾的的h序列我们都能够将其排序。
 
具体步骤：先将整个待排序的记录序列分隔成若干子序列，分别进行直接插入排序
 
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 
按增量序列个数k，对序列进行k 趟排序；
 
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 
特点
 
基于插入排序的快速排序
 
复杂度时间复杂度：O(nlogn)
 
空间复杂度：O(1)
 
非稳定排序
 
原地排序
 
使用环境
 
大型数组，大多数情况下希尔排序都是比较高效且简单的算法
 
算法代码private static void sort(int[] nums) {
 
int n=nums.length;
 
int gap=n/2;
 
while (gap>0){
 
for(int j=gap;j
 
int i=j;
 
while ((i>=gap&&nums[i-gap]>nums[i])){
 
int temp=nums[i];
 
nums[i]=nums[i-gap];
 
nums[i-gap]=temp;
 
i-=gap;
 
}
 
}
 
gap=gap/2;
 
}
 
}需要注意的是，对各个分组进行插入的时候并不是先对一个组排序完了再对另一个组排序，而是轮流对每个组进行排序。
 
归并排序
 
代码思路
 
将一个大的无序数组有序，我们可以利用归并的思想来进行排序，即将大问题化为小问题进行解决。把长度为n的输入序列分成两个长度为n/2的子序列；
 
对这两个子序列分别采用归并排序；
 
将两个排序好的子序列合并成一个最终的排序序列。
 
特点
 
速度较快，不受输入数据的影响，所需额外空间与N成正比
 
复杂度时间复杂度：O(nlogn)
 
空间复杂度：O(n)
 
稳定排序
 
非原地排序
 
使用环境
 
算法代码private static void sort(int[] nums,int start,int end) {
 
// 如果left==right，表明数组中只有一个元素，则不用递归排序
 
if(start
 
// 将大数组分割成两个小数组
 
int mid=(start+end)/2;
 
// 分别排序
 
sort(nums,start,mid);
 
sort(nums,mid+1,end);
 
// 进行合并
 
merge(nums,start,mid,end);
 
}
 
}
 
// 合并函数，把两个有序的数组合并起来
 
private static void merge(int[] nums,int left,int mid,int right){
 
int []tmp=new int[nums.length];
 
int p1=left,p2=mid+1,k=0;
 
while (p1<=mid && p2<=right){
 
if(nums[p1]<=nums[p2])
 
tmp[k++]=nums[p1++];
 
else
 
tmp[k++]=nums[p2++];
 
}
 
while (p1<=mid)
 
tmp[k++]=nums[p1++];
 
while (p2<=right)
 
tmp[k++]=nums[p2++];
 
// 把数组复制到原数组中
 
for (int i=left;i<=right;i++)
 
nums[i]=tmp[i];
 
}
 
快排(三取样切分)
 
代码思路
 
我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。
 
从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。
 
特点
 
应用广泛，原地排序，几乎不需要额外的空间
 
复杂度时间复杂度：O(nlogn)
 
空间复杂度：O(logn)
 
非稳定排序
 
原地排序
 
使用环境
 
广泛
 
算法代码private static void sort(int[] nums,int start,int end) {
 
if(nums.length<0)
 
return;
 
if(start>=end)
 
return;
 
int left=start;
 
int right=end;
 
int temp=nums[left];
 
while (left
 
while (left=temp)
 
right--;
 
nums[left]=nums[right];
 
while (left
 
left++;
 
nums[right]=nums[left];
 
}
 
nums[left]=temp;
 
sort(nums,start,left-1);
 
sort(nums,left+1,end);
 
}
 
堆排序
 
代码思路
 
利用堆这种数据结构，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
 
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
 
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
 
复杂度时间复杂度：O(nlogn)
 
空间复杂度：O(1)
 
非稳定排序
 
原地排序
 
算法代码public static void sort(int[] list) {
 
//构造初始堆,从第一个非叶子节点开始调整,左右孩子节点中较大的交换到父节点中
 
for (int i = (list.length) / 2 - 1; i >= 0; i--) {
 
headAdjust(list, list.length, i);
 
}
 
//排序，将最大的节点放在堆尾，然后从根节点重新调整
 
for (int i = list.length - 1; i >= 1; i--) {
 
int temp = list[0];
 
list[0] = list[i];
 
list[i] = temp;
 
headAdjust(list, i, 0);
 
}
 
}
 
private static void headAdjust(int[] list, int len, int i) {
 
int k = i, temp = list[i], index = 2 * k + 1;
 
while (index < len) {
 
if (index + 1 < len) {
 
if (list[index] < list[index + 1]) {
 
index = index + 1;
 
}
 
}
 
if (list[index] > temp) {
 
list[k] = list[index];
 
k = index;
 
index = 2 * k + 1;
 
} else {
 
break;
 
}
 
}
 
list[k] = temp;
 
}
 
计数排序
 
代码思路
 
计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。
 
基本思想：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。
 
复杂度时间复杂度：O(n+k)
 
空间复杂度：O(n+k)
 
稳定排序
 
非原地排序
 
使用环境
 
其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
 
算法代码public static void sortCount(int[] arr, int min, int max) {
 
int len = arr.length;
 
int[] tem = new int[max - min + 1];
 
for(int i = 0; i < len; i++) {
 
tem[arr[i] - min] += 1;
 
}
 
for(int i = 0, index = 0; i < tem.length; i++) {
 
int item = tem[i];
 
while(item-- != 0) {
 
arr[index++] = i + min;
 
}
 
}
 
}
 
桶排序
 
代码思路
 
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。设置一个定量的数组当作空桶；
 
遍历输入数据，并且把数据一个一个放到对应的桶里去；
 
对每个不是空的桶进行排序；
 
从不是空的桶里把排好序的数据拼接起来。
 
复杂度桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大
 
时间复杂度：O(n+k)
 
空间复杂度：O(n+k)
 
稳定排序
 
非原地排序
 
算法代码public static void main(String[] args) {
 
// 输入元素均在 [0, 10) 这个区间内
 
float[] arr = new float[] { 0.12f, 2.6f, 8.8f, 7.6f, 7.2f, 6.3f, 9.0f, 1.6f, 5.6f, 2.4f };
 
bucketSort(arr);
 
System.out.println(Arrays.toString(arr));
 
}
 
public static void bucketSort(float[] arr) {
 
// 新建一个桶的集合
 
ArrayList> buckets = new ArrayList>();
 
for (int i = 0; i < 10; i++) {
 
// 新建一个桶，并将其添加到桶的集合中去。
 
// 由于桶内元素会频繁的插入，所以选择 LinkedList 作为桶的数据结构
 
buckets.add(new LinkedList());
 
}
 
// 将输入数据全部放入桶中并完成排序
 
for (float data : arr) {
 
int index = getBucketIndex(data);
 
insertSort(buckets.get(index), data);
 
}
 
// 将桶中元素全部取出来并放入 arr 中输出
 
int index = 0;
 
for (LinkedList bucket : buckets) {
 
for (Float data : bucket) {
 
arr[index++] = data;
 
}
 
}
 
}
 
/**
 
* 计算得到输入元素应该放到哪个桶内
 
*/
 
public static int getBucketIndex(float data) {
 
// 这里例子写的比较简单，仅使用浮点数的整数部分作为其桶的索引值
 
// 实际开发中需要根据场景具体设计
 
return (int) data;
 
}
 
/**
 
* 我们选择插入排序作为桶内元素排序的方法 每当有一个新元素到来时，我们都调用该方法将其插入到恰当的位置
 
*/
 
public static void insertSort(List bucket, float data) {
 
ListIterator it = bucket.listIterator();
 
boolean insertFlag = true;
 
while (it.hasNext()) {
 
if (data <= it.next()) {
 
it.previous(); // 把迭代器的位置偏移回上一个位置
 
it.add(data); // 把数据插入到迭代器的当前位置
 
insertFlag = false;
 
break;
 
}
 
}
 
if (insertFlag) {
 
bucket.add(data); // 否则把数据插入到链表末端
 
}
 
}
 
基数排序
 
代码思路
 
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。取得数组中的最大数，并取得位数；
 
arr为原始数组，从最低位开始取每个位组成radix数组；
 
对radix进行计数排序(利用计数排序适用于小范围数的特点)；
 
特点
 
针对计数排序进行优化的一种算法。
 
复杂度时间复杂度：O(kn)
 
空间复杂度：O(n+k)
 
稳定排序
 
非原地排序
 
算法代码public static void main(String[] args) {
 
int[] arr = new int[] { 5,789,2138,456,3,1,9,1,13,4984,3 };
 
radixSort(arr,10000);
 
System.out.println(Arrays.toString(arr));
 
}
 
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
 
{
 
for(int num:array) //将数组array里的每个数字放在相应的桶里
 
{
 
int digit=(num/n)%10;
 
bucket[digit][order[digit]]=num;
 
order[digit]++;
 
}
 
for(int i=0;i
 
{
 
if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
 
{
 
for(int j=0;j
 
{
 
array[k]=bucket[i][j];
 
k++;
 
}
 
}
 
order[i]=0;//将桶里计数器置0，用于下一次位排序
 
}
 
n*=10;
 
k=0;//将k置0，用于下一轮保存位排序结果
 
}
 
}
 
睡眠排序
 
代码思路
 
代码思路倒是很简单，就是利用线程睡眠来进行排序，让线程睡眠、
 
特点
 
娱乐算法，没啥特点就是好玩
 
算法代码public static void sleepSort(int[] array) {
 
for (int i : array) {
 
new Thread(()->{
 
try {
 
Thread.sleep(i);
 
} catch (Exception e) {
 
e.printStackTrace();
 
}
 
System.out.println(i);
 
}).start();
 
}
 
}
 
public static void main(String[] args) {
 
int[] array = { 10, 30, 50, 60, 100, 40, 150, 200, 70 };
 
sleepSort(array);
 
}
 
随机排序排序
 
代码思路
 
就是让系统随机排序，然后验证是否有序
 
特点
 
巨复杂，看命
 
算法代码public static void randSortX(int [] array){
 
List list=new ArrayList<>();
 
for (Integer integer : array) {
 
list.add(integer);
 
}
 
int pre=0;
 
int index=0;
 
while(true){
 
pre=0;
 
for (index = 1; index < list.size(); index++) {
 
if(list.get(index)>list.get(pre)){
 
pre++;
 
}else{
 
break;
 
}
 
}
 
if(pre+1==list.size()){
 
break;
 
}
 
Collections.shuffle(list);
 
}
 
System.out.println(list.toString());
 
}
 
public static void main(String[] args) {
 
int[] array = { 10, 30, 50, 60, 100, 40, 150, 200, 70 };
 
randSortX(array);
 
}
 
最后如果觉得看完有收获，希望能给我点个赞，这将会是我更新的最大动力，感谢各位的支持
 
欢迎各位关注我的公众号【java冢狐】，专注于java和计算机基础知识，保证让你看完有所收获，不信你打我
 
如果看完有不同的意见或者建议，欢迎多多评论一起交流。感谢各位的支持以及厚爱。
 
——我是冢狐，和你一样热爱编程。
 

 
日常操作中常见的排序方法有：冒泡排序、快速排序、选择排序、插入排序、希尔排序，甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。
 
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 
/*** 冒泡法排序
 
* 
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 
* 
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 
* 
针对所有的元素重复以上的步骤，除了最后一个。
 
* 
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 
*@paramnumbers 需要排序的整型数组*/
 
public static void bubbleSort(int[] numbers) {int temp; //记录临时中间值
 
int size = numbers.length; //数组大小
 
for (int i = 0; i < size - 1; i++) {for (int j = i + 1; j < size; j++) {if (numbers[i] < numbers[j]) { //交换两数的位置
 
temp =numbers[i];
 
numbers[i]=numbers[j];
 
numbers[j]=temp;
 
}
 
}
 
}
 
}
 
快速排序使用分治法策略来把一个序列分为两个子序列。
 
/*** 快速排序
 
* 
 
* 
从数列中挑出一个元素，称为“基准”
 
* 
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后，
 
* 该基准是它的最后位置。这个称为分割(partition)操作。
 
* 
递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
 
* 
 
*
 
*@paramnumbers
 
*@paramstart
 
*@paramend*/
 
public static void quickSort(int[] numbers, int start, intend) {if (start 
 
int temp; //记录临时中间值
 
int i = start, j =end;do{while ((numbers[i] < base) && (i 
 
i++;while ((numbers[j] > base) && (j >start))
 
j--;if (i <=j) {
 
temp=numbers[i];
 
numbers[i]=numbers[j];
 
numbers[j]=temp;
 
i++;
 
j--;
 
}
 
}while (i <=j);if (start 
 
quickSort(numbers, start, j);if (end >i)
 
quickSort(numbers, i, end);
 
}
 
}
 
选择排序是一种简单直观的排序方法，每次寻找序列中的最小值，然后放在最末尾的位置。
 
/*** 选择排序
 
* 
在未排序序列中找到最小元素，存放到排序序列的起始位置
 
* 
再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
 
* 
以此类推，直到所有元素均排序完毕。
 
*
 
*@paramnumbers*/
 
public static void selectSort(int[] numbers) {int size =numbers.length, temp;for (int i = 0; i < size; i++) {int k =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;
 
}
 
}
 
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。其具体步骤参见代码及注释。
 
/*** 插入排序
 
* 
 
* 
从第一个元素开始，该元素可以认为已经被排序
 
* 
取出下一个元素，在已经排序的元素序列中从后向前扫描
 
* 
如果该元素(已排序)大于新元素，将该元素移到下一位置
 
* 
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 
* 
将新元素插入到该位置中
 
* 
重复步骤2
 
* 
 
*
 
*@paramnumbers*/
 
public static void insertSort(int[] numbers) {int size =numbers.length, temp, j;for(int i=1; i
 
temp=numbers[i];for(j = i; j > 0 && temp < numbers[j-1]; j--)
 
numbers[j]= numbers[j-1];
 
numbers[j]=temp;
 
}
 
}
 
归并排序是建立在归并操作上的一种有效的排序算法，归并是指将两个已经排序的序列合并成一个序列的操作。参考代码如下：
 
/*** 归并排序
 
* 
 
* 
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 
* 
设定两个指针，最初位置分别为两个已经排序序列的起始位置
 
* 
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
 
* 
重复步骤3直到某一指针达到序列尾
 
* 
将另一序列剩下的所有元素直接复制到合并序列尾
 
* 
 
*
 
*@paramnumbers*/
 
public static void mergeSort(int[] numbers, int left, intright) {int t = 1;//每组元素个数
 
int size = right - left + 1;while (t 
 
t = 2 *s;int i =left;while (i + (t - 1) 
 
merge(numbers, i, i+ (s - 1), i + (t - 1));
 
i+=t;
 
}if (i + (s - 1) 
 
merge(numbers, i, i+ (s - 1), right);
 
}
 
}/*** 归并算法实现
 
*
 
*@paramdata
 
*@paramp
 
*@paramq
 
*@paramr*/
 
private static void merge(int[] data, int p, int q, intr) {int[] B = new int[data.length];int s =p;int t = q + 1;int k =p;while (s <= q && t <=r) {if (data[s] <=data[t]) {
 
B[k]=data[s];
 
s++;
 
}else{
 
B[k]=data[t];
 
t++;
 
}
 
k++;
 
}if (s == q + 1)
 
B[k++] = data[t++];elseB[k++] = data[s++];for (int i = p; i <= r; i++)
 
data[i]=B[i];
 
}
 
将之前介绍的所有排序算法整理成NumberSort类，代码
 
//Java实现的排序类
 
public classNumberSort {//私有构造方法，禁止实例化
 
privateNumberSort() {super();
 
}//冒泡法排序
 
public static void bubbleSort(int[] numbers) {int temp; //记录临时中间值
 
int size = numbers.length; //数组大小
 
for (int i = 0; i < size - 1; i++) {for (int j = i + 1; j < size; j++) {if (numbers[i] < numbers[j]) { //交换两数的位置
 
temp =numbers[i];
 
numbers[i]=numbers[j];
 
numbers[j]=temp;
 
}
 
}
 
}
 
}//快速排序
 
public static void quickSort(int[] numbers, int start, intend) {if (start 
 
int temp; //记录临时中间值
 
int i = start, j =end;do{while ((numbers[i] < base) && (i 
 
i++;while ((numbers[j] > base) && (j >start))
 
j--;if (i <=j) {
 
temp=numbers[i];
 
numbers[i]=numbers[j];
 
numbers[j]=temp;
 
i++;
 
j--;
 
}
 
}while (i <=j);if (start 
 
quickSort(numbers, start, j);if (end >i)
 
quickSort(numbers, i, end);
 
}
 
}//选择排序
 
public static void selectSort(int[] numbers) {int size =numbers.length, temp;for (int i = 0; i < size; i++) {int k =i;for (int j = size - 1; j > i; j--) {if (numbers[j] 
 
k=j;
 
}
 
temp=numbers[i];
 
numbers[i]=numbers[k];
 
numbers[k]=temp;
 
}
 
}//插入排序//@param numbers
 
public static void insertSort(int[] numbers) {int size =numbers.length, temp, j;for (int i = 1; i < size; i++) {
 
temp=numbers[i];for (j = i; j > 0 && temp < numbers[j - 1]; j--)
 
numbers[j]= numbers[j - 1];
 
numbers[j]=temp;
 
}
 
}//归并排序
 
public static void mergeSort(int[] numbers, int left, intright) {int t = 1;//每组元素个数
 
int size = right - left + 1;while (t 
 
t = 2 *s;int i =left;while (i + (t - 1) 
 
merge(numbers, i, i+ (s - 1), i + (t - 1));
 
i+=t;
 
}if (i + (s - 1) 
 
merge(numbers, i, i+ (s - 1), right);
 
}
 
}//归并算法实现
 
private static void merge(int[] data, int p, int q, intr) {int[] B = new int[data.length];int s =p;int t = q + 1;int k =p;while (s <= q && t <=r) {if (data[s] <=data[t]) {
 
B[k]=data[s];
 
s++;
 
}else{
 
B[k]=data[t];
 
t++;
 
}
 
k++;
 
}if (s == q + 1)
 
B[k++] = data[t++];elseB[k++] = data[s++];for (int i = p; i <= r; i++)
 
data[i]=B[i];
 
}
 
}