常见的五种排序算法
冒泡排序
冒泡排序简介
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。
如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。大的数往下沉，小的数往下冒。 稳定、原地排序，最好时间复杂度为O(n)，最坏与平均时间复杂度为O(n2)。
原地排序简介
原地排序指的是空间复杂度为O(1)的排序算法。
稳定排序简介
稳定性指的是：如果待排序列中存在值相等的元素，经过排序之后，相等元素的先后顺序没有改变 比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。 这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。
冒泡代码代码实现
public class BubbleSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] data=new int[]{2,3,5,4,7,6,9,10,12,11,23,22,18,8};
bubbleSort(data);
for(int i=0;i<data.length;i++){
System.out.print(data[i]+" ");
}
}
public static void bubbleSort(int[] data){
if(data.length<=1) return;
for(int i=0;i<data.length;i++){
//提前退出冒泡循环的标志位
boolean flag = false;
for(int j=0;j<data.length-1-i;++j){
if(data[j]>data[j+1]){
int temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
flag = true;//有数据交换
}
}
if(!flag) break;//没有数据交换，退出
}
}
}插入排序
插入排序简介
我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。 稳定、原地排序，最好时间复杂度为O(n)，最坏与平均时间复杂度为O(n2)。
代码实现
public class InsertSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] data=new int[]{4,3,2,1,5};
insertSort(data);
for(int i=0;i<data.length;i++){
System.out.print(data[i]+" ");
}
}
public static void insertSort(int[] data){
if(data.length<=1) return;
for(int i=1;i<data.length;++i){
int value = data[i];
int j=i-1;
for(;j>=0;--j){
if(data[j]>value){
data[j+1] = data[j];
}else {
break;
}
}
data[j+1]=value;
}
}
}选择排序
选择排序简介
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。 不稳定、原地排序，最好时间复杂度为O(n2)，最坏与平均时间复杂度为O(n2)。 选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
代码实现
public class SelectSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] data=new int[]{2,3,5,4,7,6,9,10,12,11,23,22,18,8};
selectSort(data);
for(int i=0;i<data.length;i++){
System.out.print(data[i]+" ");
}
}
public static void selectSort(int[] data){
if(data.length<=1) return;
for(int i=0;i<data.length-1;++i){
int minIndex=i;
for(int j=i+1;j<data.length;++j){
if(data[j]<data[minIndex]){
minIndex = j;
}
}
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}归并排序
归并排序简介
如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。 归并排序用的是一种分治思想，它不是原地排序，即空间复杂度不是O(1)，空间复杂度为O(n),不管最好还是最坏或平均，它的时间复杂度都为O(nlogn)，是一个稳定的算法。
代码实现
/**
* 归并排序
* 将需要排序的数组从中间分成两部分，将这两部分分别排序，再将排序好的两部分合并在一起
* 时间复杂度O(nlogn)
* 空间复杂度(n)
*
*/
public class MergeSort {
public static void main(String[] args) {
int[] a= new int[]{1,2,4,3,45,34,23,6,7};
mergeSort(a, 9);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
private static void mergeSort(int[] a,int n){
mergeIntaily(a, 0, n-1);
}
private static void mergeIntaily(int[] a,int p,int r){
if(p>=r) return;
int q = p+(r-p)/2;
mergeIntaily(a, p, q);
mergeIntaily(a, q+1, r);
merge(a, p, q, r);
}
private static void merge(int[] a,int p,int q,int r){
int i=p;
int j = q+1;
int k=0;
//申请一个数组，大小与a[p..r]相同
int[] tmp = new int[r-p+1];
//用两个游标，一个i指向a[p..q]中的第一个元素,一个j指向a[q+1..r]的第一个元素,
//如果a[i]<=a[j],就将a[i]的值放进tmp数组中,i后移,否则将a[j]元素放进tmp数组中,j后移
while(i<=q&&j<=r){
if(a[i]<=a[j]){
tmp[k++] = a[i++];
}else {
tmp[k++] = a[j++];
}
}
//判断那部分数组剩余
int start = i;
int end = q;
if(j<=r){
start = j;
end = r;
}
//将剩余数组放进tmp中
while(start<=end){
tmp[k++] = a[start++];
}
//在将tmp数组中的元素放回原数组中
for(i=0;i<=r-p;i++){
a[p+i] = tmp[i];
}
}
}merge(A[p…r], A[p…q], A[q+1…r]) 这个函数的作用就是，将已经有序的 A[p…q] 和 A[q+1…r] 合并成一个有序的数组，并且放入 A[p…r]。
申请一个临时数组 tmp，大小与 A[p…r] 相同。我们用两个游标 i 和 j，分别指向 A[p…q] 和 A[q+1…r] 的第一个元素。比较这两个元素 A[i] 和 A[j]，如果 A[i]<=A[j]，我们就把 A[i] 放入到临时数组 tmp，并且 i 后移一位，否则将 A[j] 放入到数组 tmp，j 后移一位。
继续上述比较过程，直到其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组 tmp 中的数据拷贝到原数组 A[p…r] 中。
快速排序
快速排序简介
要排序的数组下标从p到r的一组数据，选取从p到r之间的任意一个数据作为pivot(分区点),也是分治思想。 快速排序是原地排序，不稳定，最坏时间复杂度为O(n2)，最好和平均时间复杂度都为O(nlogn)，空间复杂度为O(1)。
代码实现
public class QuickSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a= new int[]{1,2,4,3,45,34,23,6,7};
quickSort(a, 9);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
private static void quickSort(int[] a,int n){
quickSortIntaily(a, 0, n-1);
}
private static void quickSortIntaily(int[] a,int p,int r){
if(p>=r) return; //递归终止条件
int q= partition(a, p, r);
quickSortIntaily(a, p, q-1);
quickSortIntaily(a, q+1, r);
}
//分区函数,随机选择一个元素作为pivot，一般选取从p到r的最后一个元素，然后对a[p..r]分区，返回pivot下标
private static int partition(int[] a,int p,int r){
int pivot = a[r];
int i=p;
for(int j=p;j<r;++j){
if(a[j]<pivot){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
++i;
}
}
int tmp = a[i];
a[i] = a[r];
a[r] = tmp;
return i;
}
}遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
归并与快排区别
- 归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法；
- 归并排序和快速排序是两种稍微复杂的排序算法，都是使用分治的思想，代码都通过递归来实现，过程相似；