从第一个开始比较，找到最大的值，让其交换到数组的最后面，然后就第二大，第三大·····，不断比较，当前一个的值都比后一个的值小的时候，数组排序结束。
时间复杂度是O(n^2)
稳定性较强，因为总是相邻的两个元素在交换
public class TenAlgorithm {
public static void main(String[] args) {
int[] a={4,5,8,9,6,2,3,5,4,58,15,9};
for (int i:bubbleSort(a)) {
System.out.print(i+",");
}
}
public static int[] bubbleSort(int[] arr){
int len=arr.length;
if(arr==null||len<2){
return arr;
}
int temp=0;
for (int i = 0; i < len; i++) {
for (int j=0;j<len-i-1;j++){
if(arr[j] > arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}
}
从无序的区间不断找出最小值，挑选n-1次（最后一个元素不用挑）。与冒泡排序的不同在于，冒泡排序每次比对都要交换元素的位置，而选择排序只有经过一轮的比较后，找到这一轮最小值的下标才会去交换元素，相比之下节省了不少的资源。
时间复杂度：O（n^2）
稳定性较差，因为有可能第一个和最后一个元素交换
public static int[] selectSort(int[] arr){
int len=arr.length;
if(arr==null||len<2){
return arr;
}
for (int i = 0; i <len; i++) {
int minIndex=i;
for (int j = i+1; j <len; j++) {
if(arr[minIndex]>arr[j]){
minIndex=j;
}
}
swap(arr,minIndex,i);
}
return arr;
}
public static void swap(int[] arr,int minIndex,int i){
int temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
插入排序就是把未排序的元素插入到已排序的数组中。
把左边的第一位看做已经排好序的数组，右边的为没有拍好序的数组，通过向左边一个个的插入右边的元素从而实现数组的排序。
从数组的第二个元素开始遍历，在进入第一个循环后，需要保存当前位置元素。然后进行比较，如果前一个元素大于保存的元素，则前一个元素向后移动一位，一直如此，直到前一个元素小于保存的元素时，停止。
然后跳出内循环，因为当前j位置的元素是小于保存的元素，并且其后一个的元素已经向后移动了一位，所以保存的元素要插入的位置是j+1。
时间复杂度：O（n^2）
稳定性较强，因为在相邻的元素中移动
public static int[] insertionSort(int[] arr){
int len=arr.length;
if(arr==null||len<2){
return arr;
}
for (int i = 1; i < len; i++) {
int insert=arr[i];
int j=i-1;
for (; j>=0&&arr[j] >insert ; j--) {
//如果前一个大于后一个，则移动前一个到后面
arr[j+1]=arr[j];
}
arr[j+1]=insert;
}
return arr;
}
小规模数据或者基本有序时高效（数据有序程度越高，越高效（移动少））
首先把一个较大的数据集合分割成若干个小组（逻辑上的分组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高。
{9，8，7，6，5，4，3，2}这种，一开始以4为间隔，就是{9，5}，{8，4}，{7，3}，{6，2}，对里面的进行插入排序得到{5，4，3，2，9，8，7，6}，然后再长度对半为2分组，就是{5，3，9，7}，{4，2，8，6}得到{3，2，5，4，7，6，9，8}，再重复上面的操作，最后得到{2，3，4，5，6，7，8，9}。public static int[] shellSort(int[] arr){
int len=arr.length;
if(arr==null||len<2){
return arr;
}
//进行分组，最开始时的增量为数组长度的一半
for (int gap =len/2 ; gap>0; gap/=2) {
//比较完一组后，再移动下一组（按一组组这样进行插入排序）
for (int i = gap; i < len; i++) {
int insertValue=arr[i];
//j已经移到第前grap个了
int j=i-gap;
//插入的时候按组进行插入（组内元素两两相隔gap）
for (; j >=0 &&insertValue<arr[j]; j-=gap) {
arr[j+gap]=arr[j];
}
arr[j+gap]=insertValue;
}
}
return arr;
}
希尔排序的复杂度和增量序列是相关的
{1,2,4,8,…}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n^2)
Hibbard提出了另一个增量序列{1,3,7，…,2^k-1}，这种序列的时间复杂度(最坏情形)为O(n ^ 1.5)
Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是{1,5,19,41,109,…}
归并排序是建立在归并操作的一种高效的排序方法，该方法采用了分治的思想，比较适用于处理较大规模的数据，但比较耗内存。
public static int[] mergeSortArr(int[] arr){
int len=arr.length;
if(arr==null||len<2){
return arr;
}
int[] temp=new int[len];
//right的长度为len-1，因为从0开始
mergeSort(arr,temp,0,len-1);
return arr;
}
private static void mergeSort(int[] arr, int[] temp, int left, int right) {
//当left==right是停止
if(left<right){
//分，将数组二分
int center=left+(right-left)/2;
//左边left->center
mergeSort(arr,temp,left,center);
//右边center+1->right
mergeSort(arr,temp,center+1,right);
//合并数组
merge(arr,temp,left,center,right);
}
}
private static void merge(int[] arr, int[] temp, int left, int center, int right) {
int i=left,j=center+1;
for (int k = left; k <=right; k++) {
//如果i大于center，表示i的数组已经赋值完，不需要再比较，直接copy数组j
//如果j大于right，表示j的数组已经赋值完，不需要再比较，直接copy数组i
if(i>center){
temp[k]=arr[j++];
}else if(j>right){
temp[k]=arr[i++];
}else if(arr[i]<=arr[j]){
temp[k]=arr[i++];
}else {
temp[k]=arr[j++];
}
}
//从临时数组传回原来数组
for (int k = left; k <=right; k++) {
arr[k]=temp[k];
}
}
时间复杂度：O（N log N）
稳定性较为稳定，因为在合并的时候，如果相等，选择前面的元素到辅助数组。
时间复杂度：O（nlogn），最坏的情况为O(n^2)
稳定性较差
它不像归并排序那样，需要额外的辅助空间，而且在分割调整的时候，不像归并排序那样，元素还要在辅助数组与源数组之间来回复制。
/**
* 快速排序
*
* @param arr
* @return int[]
*/
public static int[] partitionSort(int[] arr) {
int len = arr.length;
if (arr == null || len < 2) {
return arr;
}
partition(arr, 0, len - 1);
return arr;
}
private static void partition(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[left];
int i = left + 1, j = right;
while (i < j) {
while (i <= j && arr[i] <= pivot) {
i++;
}
while (i <= j && arr[j] >= pivot) {
j--;
}
if (i >= j) {
break;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
if (pivot > arr[j]) {
arr[left] = arr[j];
arr[j] = pivot;
}
partition(arr, left, j - 1);
partition(arr, j + 1, right);
}
基本思想：把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如temp[i]=m，表示元素i一共出现了m次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来的数据是有序的。
时间复杂度：O（n）
private static int[] countSort(int[] arr){
int len = arr.length;
if (arr == null || len < 2) {
return arr;
}
int min=arr[0];
int max=arr[0];
//寻找数组的最大值与最小值
for (int i = 0; i < len; i++) {
if(max<arr[i]){
max=arr[i];
}
if(min>arr[i]){
min=arr[i];
}
}
int d=max-min+1;
//创建大小为max的临时数组
int[] temp=new int[d];
//统计元素i出现的次数
for (int i = 0; i < len; i++) {
temp[arr[i]-min]++;
}
int k=0;
//把临时数组统计好的数据汇总到原数组
for (int i = 0; i < d; i++) {
for (int j = temp[i]; j >0 ; j--) {
arr[k++]=i+min;
}
}
return arr;
}
参考：https://www.iamshuaidi.com/608.html
因篇幅问题不能全部显示，请点此查看更多更全内容