冒泡排序，选择排序，插入排序（直接插入，二分插入，希尔排序），快速排序，堆排序，归并排序，计数排序，桶排序，基数排序。
冒泡排序：
基本思想是:两两比较相邻记录的关键字,如果反序则交换
public class BubbleSort {
public static void main(String[] args) {
int a[] ={345,54,66,3,76,345,7,4,3} ;
for(int i=0;i<a.length;i++)
for(int j=0;j<a.length-i-1;j++) {
if(a[j]>a[j+1]){
int temp;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
}
选择排序：
算法思想：将待排序序列分为两部分，一部分为有序序列，另一部分为无序序列。第一趟：从a[0]到a[n-1]中找到最小的数a[i]，然后将a[i]与a[0]交换，第二趟：从a[1]到a[n-1]中找到最小的数a[j]，然后将a[j]与a[1]交换,第三趟：从a[2]到a[n-1]中找到最小的数a[k],然后将a[k]与a[2]交换 ……
public class SelectSort {
public static void main(String[] args) {
int a[] ={345,54,66,3,76,345,7,4,3} ;
for(int i = 0;i<a.length;i++){
int min = a[i];
for(int j = i+1;j<a.length;j++){
if(min>a[j]){
int temp;
temp = min;
min = a[j];
a[j] = temp;
}
}
a[i] = min;
}
}
}
插入排序:
算法思想：
1〉从第一个元素开始，该元素可以认为已经被排序
2〉取出第一个未排序元素存放在临时变量temp中，在已经排序的元素序列中从后往前扫描，逐一比较
3〉如果temp小于已排序元素，将该元素移到下个位置
4〉重复步骤3〉，直到找到已排序的元素小于或者等于
public class InsertSort {
public static void main(String[] args) {
int a[] ={345,54,66,3,76,345,7,4,3} ;
a = insertSort(a);
String s = Arrays.toString(a);
System.out.println(s);
}
public static int[] insertSort(int[] ary){
for(int i = 1;i < ary.length;i++){
int temp = ary[i];
int j;
for(j = i-1;j>=0 && temp < ary[j];j--){
ary[j+1] = ary[j];
}
ary[j+1] = temp;
}
return ary;
}
}
快速排序：（时间复杂度nlogn， 空间复杂度nlogn）
思路：冒泡+二分+递归分治
对于给定的一组记录，选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分，直到序列中的所有记录均有序为止。
java代码：
public class QuickSort{
public static void sort(int a[], int low , int height){
int i , j, index;
if(low > height){
return;
}
i = low;
j = height;
index = a[i]; //记录下基准数
while( i < j){
while(i < j && a[j] >= index)
j--;
if(i < j)
a[i++] = a[j];
while(i < j && a[i] <= index)
i++;
if(i < j)
a[j--] = a[i]
}
a[i] = index;
sort(a, low, i-1);
sort(a, i+1, height);
}
public static void main(String[] args){
int[] a = {23,5,65,3,7,23,76,24,674,74567,2};
sort(a,0,a.length-1);
System.out.print(Arrays.toString(a));
}
}
堆排序：（时间复杂度O(nlgn)）
堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
思想：简单选择排序的升级版，思想就是将每一次的选择排序的结构记录下来。第一步先将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次最大值。如此反复执行，就能得到一个有序序列了。
问题1：如何由一个无序序列建成一个堆？可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。
问题2：在输出堆顶元素之后，如何将剩余元素成为一个新的堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。
java 代码：
public class HeapSort{
/** 堆排序 */
private static void heapSort(int[] arr) {
// 将待排序的序列构建成一个大顶堆
for (int i = arr.length / 2; i >= 0; i--){
heapAdjust(arr, i, arr.length);
}
// 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
}
}
/** 构建堆的过程, arr 需要排序的数组, i 需要构建堆的根节点的序号,n 数组的长度*/
private static void heapAdjust(int[] arr, int i, int n) {
int child;
int father;
for (father = arr[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
// 如果左子树小于右子树，则需要比较右子树和父节点
if (child != n - 1 && arr[child] < arr[child + 1]) {
child++; // 序号增1，指向右子树
}
// 如果父节点小于孩子结点，则需要交换
if (father < arr[child]) {
arr[i] = arr[child];
} else {
break; // 大顶堆结构未被破坏，不需要调整
}
}
arr[i] = father;
}
// 获取到左孩子结点
private static int leftChild(int i) {
return 2 * i + 1;
}
// 交换元素位置
private static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
}
注：例外一种建堆的方式：（一个一个插入堆，小顶堆）
public void insertMinHeap(int arr[], int i){
int parent = (i-1) / 2;
while(parent >= 0&& arr[i] < arr[parent]){
//如果父亲节点的下标大于0，并且当前节点小于父节点交换位置。继续向上比较，否则停止比较
if( i == 0)
break;
int temp = arr[parent];
arr[parent] = arr[i];
arr[i] = temp;
i = parent;
parent = (i - 1) / 2;
}
}
java api 中关于插入堆的操作(小顶堆)
private void siftUp(int t, int arr[] ){
int key = arr[k];
while (k > 0){
int parent = ( k -1) >>>1;
int e = arr[parent];
if(arr[parent] < arr[k])
break;
k = parent;
}
arr[k] = key;
}
希尔排序
希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：(1)先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。（2）增量初值通常为数据序列长度的一半，以后每趟增量减半，最后值为1。随着增量逐渐减小，组数也减小，组内元素个数增加，数据序列接近有序。
java 实现：
（1）最外层循环for语句以增量d变化控制进行若干趟扫描，d的初值为序列长度的一半，以后每趟减半，直至为1；
（2）中间for循环进行一趟扫描，序列分为d组，每组由相距为d远的n/d个元素组成，每组元素分别进行直接插入排序；
（3）最内层循环for语句进行一组直接插入排序，将一个a[i]插入到其所在组前面的排序子序列中。
public void shellsort(int[] a){
for(int d=a.length/2;d>0;d=d/2) {
System.out.println("d="+d);
for(int i=d;i<a.length;i=i+d) {
int temp=a[i];
int j;
for(j=i-d;j>=0&&temp<a[j];j=j-d) {
a[j+d]=a[j];
}
a[j+d]=temp;
}
}
}
归并排序
基本原理：（1）对于给定的一组记录，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序，最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。 （2）经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录并与第二个位置记录交换；重复该过程，知道进行比较的记录只剩下一个为止。
public class MergeSort {
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = a[i++];
}
// 把右边剩余的数移入数组
while (j <= high) {
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
a[k2 + low] = temp[k2];
}
}
public static void mergeSort(int[] a, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
mergeSort(a, low, mid);
// 右边
mergeSort(a, mid + 1, high);
// 左右归并
merge(a, low, mid, high);
System.out.println(Arrays.toString(a));
}
}
public static void main(String[] args) {
int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
mergeSort(a, 0, a.length - 1);
System.out.println("排序结果：" + Arrays.toString(a));
}
}
计数排序(O(n))
计数排序需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
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;
}
桶排序
桶排序的基本思想是：把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。
计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
1.找出待排序数组中的最大值max、最小值min
2.我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
3.遍历数组 arr，计算每个元素 arr[i] 放的桶
4.每个桶各自排序
5.遍历桶数组，把排序好的元素放进输出数组
public static void buckerSort(int[] arr){
int max = Integer.MAX_VALUE;
int min = Integer.MIN_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//桶数
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
//将每个元素放入桶
for(int i =0; i< arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
System.out.print(bucketArr.toString());
}
基数排序
基数排序思想：基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面。如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。
关键：1.怎么保留前一位的排序结果，这个问题用之前提到的排序稳定性可以解决。2.怎么关联该位排序结果和原数组元素，二维数组正是为了解决这个问题使用的办法。
package sort;
public class RadixSort {
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 < d) {
//将数组array里的每个数字放在相应的桶里
for(int num : array) {
int digit = (num/n)%10;
bucket[digit][order[digit]]=num;
order[digit]++;
}
//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
for(int i = 0; i <length; i++){
if(order[i] != 0) //这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中 {
for(int j = 0; j < order[i]; j++) {
array[k]=bucket[i][j];
k++;
}
}
order[i] = 0; //将桶里计数器置0，用于下一次位排序
}
n*=10;
k=0; //将k置0，用于下一轮保存位排序结果
}
}
public static void main(String[] args){
int[] A = new int[]{73,22, 93, 43, 55, 14, 28, 65, 39, 81};
radixSort(A, 100);
for(int num : A){
System.out.println(num);
}
}
}
