排序算法有很多，包括插入排序，冒泡排序，堆排序，归并排序，选择排序，计数排序，基数排序，桶排序，快速排序等。插入排序，堆排序，选择排序，归并排序和快速排序，冒泡排序都是比较排序，它们通过对数组中的元素进行比较来实现排序，其他排序算法则是利用非比较的其他方法来获得有关输入数组的排序信息。
冒泡排序
冒泡排序,不稳定（会改变大部分部分数组数值的位置）
冒泡排序每次出来一个最值是其核心算法所在
冒泡排序的时间复杂度：
冒泡排序的最好情况下时间复杂度为O(n)；最坏的情况下时间复杂度为O(n^2)。
冒泡排序的次数：
N个数比较N-1遍。
原理：
对于一个数组，冒泡排序算法会比较相邻的两项的大小，并进行交换。
对每一对相邻的元素做同样的调整，如：第一个和第二个，第二个和第三个，第三个和第四个等等，以此类推。这样下来，最后的元素会是最大的。
重复以上步骤。如果有n个元素，则第一次循环进行n-1次，第二次循环进行n-2次，…………，第n-j次循环过后，会按大小顺序排出j个较大的数。
持续以上的步骤，直到没有任何一堆数字需要比较。
思路：
依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
举例说明：要排序数组：int[] array={6,3,8,2,9,1};
public class BubbleSort {
/**
* N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数。
* @param args
*/
public static void main(String[] args) {
int arr[] = {26,15,29,66,99,88,36,77,111,1,6,8,8};
for(int i=0;i < arr.length-1;i++) {//外层循环控制排序趟数
for(int j=0; j< arr.length-i-1;j++) {
//内层循环控制每一趟排序多少次
// 把小的值交换到前面
if (arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.print("第"+(i+1)+"次排序结果：");
//列举每次排序的数据
for(int a=0;a<arr.length;a++) {
System.out.print(arr[a] + "\t");
}
System.out.println("");
}
System.out.println("最终排序结果：");
for(int a = 0; a < arr.length;a++) {
System.out.println(arr[a] + "\t");
}
}
}选择排序
选择排序（Selection sort）是一种简单直观的排序算法。
选择排序，不稳定（会改变大部分数组原本位置的值）
选择排序是拿每一个数和其后面所有的数比较
工作原理是：
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法
{8 , 2 , 3 , 7 , 1}
第 1 轮：{1 | 8 , 3 , 7 , 2}
第 2 轮： {1 , 2 | 8 , 7 , 3}
第 3 轮： {1 , 2 , 3 | 8 , 7}
第 4 轮： {1 , 2 , 3 , 7 | 8}
第 5 轮： {1 , 2 , 3 , 7 | 8}
选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换
选择排序的时间复杂度：
选择排序的时间复杂度为 O(n^2)。
举例说明：
public static void selectionSort(int[] arr){
int min, temp;
for (int i = 0; i < arr.length; i++) {
// 初始化未排序序列中最小数据数组下标
min = i;
for (int j = i+1; j < arr.length; j++) {
// 在未排序元素中继续寻找最小元素，并保存其下标
if (arr[j] < arr[min]) {
min = j;
}
}
// 将未排序列中最小元素放到已排序列末尾
if (min != i) {
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}插入排序
插入排序，稳定（改变一部分数组数值的位置）（时间最坏复杂度 O(n^2)最优均为O(n))
插入排序的算法核心为把当前插入的位置之前变为有序
原理：将n个元素的数列分为已有序和无序两个部分，如插入排序过程示例下所示：
{{a1}，{a2，a3，a4，…，an}}
{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}
{{a1(n-1），a2(n-1) ，…},{an(n-1)}}
例如，{101, 34, 119, 1}逐步推导
第1轮 {101, 34, 119, 1}; => {34, 101, 119, 1}
{101, 34, 119, 1}; => {101,101,119,1}
{101,101,119,1}; => {34,101,119,1}
第2轮 {34, 101, 119, 1}; => {34, 101, 119, 1}
第3轮 {34, 101, 119, 1}; => {1, 34, 101, 119}
{34, 101, 119, 1}; => {34, 101, 119, 119}
{34, 101, 119, 119}; => {34, 101, 101, 119}
{34, 101, 101, 119}; => {34, 34, 101, 119}
{34, 34, 101, 119}; => {1, 34, 101, 119}
插入排序适合的两种情况：
每一个元素距离其最终位置不远的时候选择
对于元素较少的数组我们插入排序最快（如果N过于小受系数影响）
每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。
代码演示
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] array={12,73,45,69,35};
int i,j,temp;
for(i=1;i<array.length;i++) {
/*
* 第一个for循环
* 把数组分成两部分，右边为未排序，左边为已排序
* 记录排序与未排序分割点temp（temp为下一个排序对象）
*/
temp=array[i];
for(j=i-1;j>=0;j--) {
/*
* 第二个for循环
* 将排序对象temp与已排序数组比较
* 当temp比最近左边的数大时（按从小到大循序排列时）
* 直接结束本次循环，进行下一个数排序
* 否则比左边这个数小时将这个数后移，腾出这个数的位置
*/
if (temp > array[j]) {
break;
}else{
array[j+1] = array[j];
}
}
array[j+1]=temp;
}
System.out.println(Arrays.toString(array));
}
}
计数排序
计数排序适用于当前数组密集的情况。例如(2,3,5,4,2,3,3,2,5,4)
方法：
先找出最大值最小值，之后统计每个数出现的次数，根据次数从小到大往数组里添加
计数排序法是一种不需要比较的排序方法
核心思想：
将数字和角标进行规整
计数排序思路
计数排序适用于有明确范围的数组，比如给定一个数组，且知道所有值得范围是[m,n]。这个时候可以使用一个n-m+1长度的数组，待排序的数组就可以散在这个数组上，数组的值就是当前值的个数，再经过一次遍历展开，得到的数组就有序了。
- 新建一个长度为n-m+1的临时数组
- 遍历待排序数组，它的值-m作为临时数组下角标，这个位置的值加1
- 遍历结束，临时数组就存储了每个值得个数
- 最后将它展开赋值给原数组
代码
1 //计数排序
2 void CountSort(int *a, int size)
3 {
4 int max = a[0];
5 int min = a[0];
6 for (int i = 0; i < size; ++i)
7 {
8 if (a[i] > max)
9 max = a[i];
10 if (a[i] < min)
11 min = a[i];
12 }
13 int range = max - min + 1; //要开辟的数组范围
14 int *count = new int[range];
15 memset(count, 0, sizeof(int) * range); //初始化为0
16 //统计每个数出现的次数
17 for (int i = 0; i < size; ++i) //从原数组中取数，原数组个数为size
18 {
19 count[a[i] - min]++;
20 }
21 //写回到原数组
22 int index = 0;
23 for (int i = 0; i < range; ++i) //从开辟的数组中读取，开辟的数组大小为range
24 {
25 while (count[i]--)
26 {
27 a[index++] = i + min;
28 }
29 }
30 delete[] count;
31 }四种排序汇总：
class Test02{
public static void main(String[] args){
//1.选择排序O(n^2)
selectSort();
//2.冒泡排序O(n^2)
bubbleSort();
//3.插入排序O(n^2)
insertSort();
//4.计数排序O(n+m)
/*
上述三个排序都是根据数据之间的大小关系进行比较排序的
计数 基数 桶 都是根据数据本身的特性比较 与大小无关的排序
这些排序只针对整数
是一个典型的牺牲空间换时间的排序
*/
countSort();
}
public static void countSort(){
int[] arr={8,5,9,2,7,4,6,1,3,10,-3,-2,-10};
int min=arr[0];
int max=arr[0];
for(int i=0;i<arr.length;i++){//O(n)
if(arr[i]>max){
max=arr[i];
}
if(arr[i]<min){
min=arr[i];
}
}
int[] nums=new int[max-min+1];
int offset=min;
for(int i=0;i<arr.length;i++){//O(n)
nums[arr[i]-offset]++;
}
int index=0;
for(int i=0;i<nums.length;i++){//O(m)
if(nums[i]!=0){
for(int j=0;j<nums[i];j++){
arr[index++]=i+offset;
}
}
}
show(arr);
}
public static void insertSort(){
int[] arr={8,5,9,2,7,4,6,1,3};
int e;
int j;
for(int i=1;i<arr.length;i++){
e=arr[i];
for(j=i;j>0&&arr[j-1]>e;j--){
arr[j]=arr[j-1];
}
arr[j]=e;
}
/*
for(int i=1;i<arr.length;i++){
for(int j=i;j>0&&arr[j-1]>arr[j];j--){
swap(arr,j,j-1);
}
}
*/
show(arr);
}
//如何优化自己看 反正我讲了 你们自己回去写代码 不要求
public static void bubbleSort(){
int[] arr={8,5,9,2,7,4,6,1,3};
for(int i=0;i<arr.length-1;i++){//-1是少一轮比较
for(int j=0;j<arr.length-1-i;j++){//-1避免重复比较和角标越界
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
show(arr);
}
public static void selectSort(){
int[] arr={8,5,9,2,7,4,6,1,3};
for(int i=0;i<arr.length-1;i++){//-1是因为没有必要进行最后一个数字的比较
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
swap(arr,i,j);//即用-即释放
}
}
}
show(arr);
}
public static void swap(int[] arr,int i,int j){
//1.借助三方变量进行交换
//适用于所有的数据类型 比较通用
/*
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
*/
//2.借助加减法运算进行交换
//只适用于数字相关的数据类型
arr[i]=arr[i]+arr[j];
arr[j]=arr[i]-arr[j];
arr[i]=arr[i]-arr[j];
//3.借助位运算进行交换
//只适用于整数相关的数据类型
/*
int a=3;
int b=7;
a=a^b;
0011
0111
0100
b=a^b;
0100
0111
0011 ->3
a=a^b;
0100
0011
0111 ->7
*/
}
public static void show(int[] arr){
//[1,2,3,4,5,6,7,8,9]
String s="[";
for(int i=0;i<arr.length;i++){
if(i==arr.length-1){
s+=arr[i]+"]";
}else{
s+=arr[i]+",";
}
}
System.out.println(s);
}
}