插入排序、冒泡排序、选择排序、快速排序、归并排序
以下所有排序都是实现升序
1.插入排序
【定义】
第一个元素自成一个有序数组A，从第二个元素开始，把每一个元素插入到有序数组A中合适的位置，满足有序的条件。直到最后元素，至此构建成一个有序数组。
【时间复杂度】
O(n2)
【代码】
public void method(int [] array) {
int length = array.length;
int i,j;
for (i = 1; i < length; i++) {
int temp = array[i];
for (j = i-1; j >= 0 && array[j] > temp; j --) {
array[j+1] = array[j];
}
array[j+1] = temp;
}
}
补充：
在第二个for循环中，判断条件需要加上比较大小关系，
不能在for循环里面进行if判断，因为这样会导致最后一个元素的判断存在问题
2.冒泡排序
【定义】
从第一个元素开始，进行两两比较，如果前一个大于后一个，则进行交换，经过一轮交换之后，也就是一次冒泡，最大的元素就会在最后一个位置，在从第一个元素进行排序，两两比较，经过一轮交换之后，第二大的元素就在倒数第二个位置，以此类推
【时间复杂度】
O(n2)
【代码】
public void method(int [] a) {
int i,j;
for (i = a.length; i > 0; i --) {
for (j = 0; j < i-1; j ++) {
if (a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
改进：
可以通过加标志位，当一次冒泡没有发生交换的时候，
也就意味着此时是排好序的
public void BetterMethod(int [] a) {
int i,j;
boolean flag = false;
for (i = a.length; i > 0; i --) {
flag = false;
for (j = 0; j < i-1; j ++) {
if (a[j] > a[j+1]) {
flag = true;
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
if (!flag) {
break;
}
}
}
3.选择排序
【定义】
在第一个元素到最后一个元素之间寻找一个最小的元素放在第一位，在从第二个元素到最后一个元素选择一个最小的放在第二位，依次类推
【时间复杂度】
O(n2)
【代码】
public void method(int [] a) {
int i,j;
for (i = 0; i < a.length-1; i++) {
int index = i;
for (j = i+1; j < a.length; j++) {
if (a[j] < a[index]) {
index = j;
}
}
if (i != index) {
int temp = a[i];
a[i] = a[index];
a[index] = temp;
}
}
}
4.快速排序
【定义】
快速排序需要通过递归的方法来实现，首先需要选择一个支点，这个支点理论是可以任意选择，但通常都选择中间的元素，然后从在头和尾放置索引开始同时向中间遍历，当头索引遇到大于支点的元素停止，当尾索引遇到小于支点的元素停止，然后交换头尾索引的元素，之后头尾索引交叉停止，递归的遍历，直到首尾相等
【时间复杂度】
O(nlogn)
【代码】
public class QuickSort {
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i<j) {
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
【注意】
选准基准点之后，首尾设置索引，需要先从右向左遍历，在从左向右遍历，这里顺序不能颠倒，颠倒顺序算法就错误，因为一次快排要达到左边元素都小于基准点，右边元素都大于基准点，如果先从左边开始，会在大于基准点的位置停止，这个时候在交换，会在这个大于的元素跟基准点交换。
在内层的索引while循环的条件：temp<=arr[j]&&i<j，中的等于号不能省略，因为首索引从基准点开始，索引要保证完全大于或小于才跳出循环。
在外层的while循环结束之后，i和j一定是相等的，此时递归的条件，写i和j都可以。
5.归并排序
【定义】
二路归并排序需要通过递归实现，运用的是分而治之的思想，先分再合，先是不断的分元素，直到每组元素只能一个，然后是合并，合并的时候，以中间为区分，分别在两组的首元素上设置索引，构建一个临时数组，比较索引所在的元素并把较小的放入临时数组，直到其中一组元素为空，这个时候再把另一组的元素全部放入临时数组。最后把临时数组元素拷贝到目标数组
【时间复杂度】
O(nlogn)
【代码】
/**
* 排序
* */
public void sort(int [] a,int s, int e) {
// 当只剩一个元素返回
if (s < e) {
// 获取中间下标
int mid = (s + e)/2;
sort(a, s, mid);
sort(a, mid+1, e);
// 合并两个组的元素
merge(a, s, mid, e);
}
}
/**
* 合并元素
* */
public void merge(int [] a,int s, int mid, int e) {
// 临时数组
int [] temp = new int[e-s+1];
int i = s;
int j = mid + 1;
int index = 0;
// 把两组元素比较，并以此放入临时数组，直到其中一组元素为空
while (i<=mid && j<=e) {
if (a[i] < a[j]) {
temp[index ++] = a[i ++];
} else {
temp[index ++] = a[j ++];
}
}
// 把剩下的不为空的一组元素放入临时数组
while (i <= mid) {
temp[index ++] = a[i ++];
}
while (j <= e) {
temp[index ++] = a[j ++];
}
// 把临时数组复制到目标数组
index = 0;
while (s <= e) {
a[s ++] = temp[index ++];
}
}
稳定性
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。
选择排序、希尔排序（插入排序的一种改进）、快速排序、堆排序是不稳定的。
关于快排和归并排序
快排的最坏时间复杂度是n2,归并的最好最坏都是nlogn
归并的速度开始超过快速排序了，因为归并排序比快排要稳定，所以在数据量大的时候，快排容易达到 O (n^2) 的时间复杂度，所以大量数据二路归并排序是更好的选择
网友评论