一.分类：
1）插入排序（直接插入排序、希尔排序）
2）交换排序（冒泡排序、快速排序）
3）选择排序（直接选择排序、堆排序）
4）归并排序
5）分配排序（基数排序）
所需辅助空间最多：归并排序
所需辅助空间最少：堆排序
平均速度最快：快速排序
不稳定：快速排序，希尔排序，堆排序。
先来看看 8种排序之间的关系：
二.常见排序
1.冒泡排序（BubbleSort）
1.依次比较相邻的两个元素，通过一次比较把未排序序列中最大（或最小）的元素放置在未排序序列的末尾。
2.原理图
public class BubbleSort {
public static void main(String[] args) {
int[] a = {1,42,354,6,5,7,74,4,675,6,45345,3,64,3,4,365,34,3,43,45,34,563,64,457,546,4};
int temp =0;
for (int i = 0; i < a.length-1; i++) { //n个数比较n-1次
for (int j = 0; j < a.length-1-i; j++) { //注意j的范围
if (a[j]>a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] =temp;
}
}
}
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]); //遍历排序好的数组
}
}
}
2.快速排序（QuickSort）
1.基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
2.原理图
public class QuickSort {
public static void sort(int data[], int start, int end) {
if (end - start <= 0) {
return;
}
int last = start;
for (int i = start + 1; i <= end; i++) {
if (data[i] < data[start]) {
int temp = data[++last];
data[last] = data[i];
data[i] = temp;
}
}
int temp = data[last];
data[last] = data[start];
data[start] = temp;
sort(data, start, last - 1); //排序所在数的前一部分
sort(data, last + 1, end); //排序所在数的后一部分
}
public static void main(String[] args) {
int[] a = {1,42,354,6,5,7,74,4,675,6};
sort(a, 0, a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]); //遍历已经排序好的数组
}
}
}
3.插入排序(InsertSort)
1.将数列分为有序和无序两个部分，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。
2.原理图
public class InsertSort {
public static void Insert(int data[]) {
for (int i = 1; i < data.length; i++) {
for (int j = i; j > 0; j--) { //随着i值增大，j值每次插入的次数也增大
if (data[j] < data[j - 1]) {
int temp = data[j];
data[j] = data[j - 1];
data[j - 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] a = {1,42,354,6,5,7,74,4,675,6};
Insert(a);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]); //遍历已经排序好的数组
}
}
}
4.选择排序（SelectionSort）
1.基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
2.原理图
public class SelectionSort {
public static void selectionSort(int data[]){
for (int i = 0; i < data.length-1; i++) {
int minVal = data[i];
int minIndex = i;
for (int j = i+1; j < data.length; j++) {
if (data[j]<minVal) { //将当前数与minVal比较
minVal = data[j]; //如果当前数小于minVal则把当前数赋给minVal
minIndex = j; //把当前索引赋给minIndex
}
}
if(minVal != data[i] && minIndex != i){ //如果上一步有交换
data[minIndex] = data[i];//则把当前数放到当前最小数组的位置，如此反复
data[i] = minVal;
}
}
}
public static void main(String[] args) {
int[] a = {1,42,354,6,5,7,74,4,675,6,45345,3,64,3,4,365,34,3,43,45,34,563,64,457,546,4};
selectionSort(a);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);//遍历排序好的数组
}
}
}