1.冒泡排序
2.选择排序
3.插入排序
4.快速排序
5.堆排序
6.希尔排序
7.归并排序
8.计数排序
9.桶排序
10.基数排序
该篇排序方式：由小到大排序
1.冒泡排序
从后向前冒泡
从前向后冒泡
由小到大，从后向前冒泡：[90，78，65，43，20]
一次冒泡
第一次比较：[90，78，65，20，43] 一次交换操作
第二次比较：[90，78，20，65，43] 一次交换操作
第三次比较：[90，20，78，65，43] 一次交换操作
第四次比较：[20，90，78，65，43] 一次交换操作
二次冒泡
第一次比较：[20，90，78，43，65] 一次交换操作
第二次比较：[20，90，43，78，65] 一次交换操作
第三次比较：[20，43，90，78，65] 一次交换操作
三次冒泡
第一次比较：[20，43，90，65，78] 一次交换操作
第二次比较：[20，43，65，90，78] 一次交换操作
四次冒泡
第一次比较：[20，43，65，78，90] 一次交换操作
共十次交换操作
1.最后一个元素与相邻元素对比
2.小于相邻元素，则交换
3.大于等于相邻元素，无需交换，继续相邻元素的对比
4.直到与最左边的元素对比完成，一次冒泡结束
5.对剩下的序列，重复1~4的步骤
6.直到剩下的序列长度为1，整个冒泡结束
1.不使用递归实现
/**
* 冒泡排序
*
* 由小到大排序
*
* 从后向前冒泡
*
* @param arr
*/
public void bubbleSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = arr.length - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j - 1, j);
}
}
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
2.使用递归方式实现
/**
*
*冒泡排序函数
*/
public void sortByBubble(int[] paramInts) {
sortByBubble(paramInts, 0);
}
/**
*
*冒泡排序的辅助方法
*paramInts:排序的数组对象
*index:序列最左边下标
*/
private void sortByBubble(int[] paramInts, int index) {
if (index == paramInts.length - 1) {
return;
}
for (int i = paramInts.length - 1; i > index; i--) {
if (paramInts[i] < paramInts[i - 1]) {
int tempValue = paramInts[i];
paramInts[i] = paramInts[i - 1];
paramInts[i - 1] = tempValue;
}
}
sortByBubble(paramInts, index + 1);
}
从前向后冒泡
1.第一个元素与相邻的元素对比
2.小于相邻元素，则交换
3.大于等于相邻元素，无需交换，继续相邻元素的对比
4.直到与最右边元素对比完成，一次冒泡结束
5.对剩下的序列，重复1~4的步骤
6.直到剩下的序列长度为1，完成整个数组的冒泡
1.一次冒泡过程不使用递归实现
public void sortByBubble(int[] paramInts) {
sortByBubble(paramInts, paramInts.length - 1);
}
/**
*
*由前向后冒泡排序的辅助方法
*paramInts:排序数组对象
*index:序列最右边的下标
*/
private void sortByBubble(int[] paramInts, int index) {
if (index == 0) {//没有可冒泡的序列了
return;
}
for (int i = 0; i < index; i++) {
if (paramInts[i + 1] > paramInts[i]) {//小于相邻元素
//与相邻元素交换
int tempValue = paramInts[i];
paramInts[i] = paramInts[i + 1];
paramInts[i + 1] = tempValue;
}
}
sortByBubble(paramInts, index - 1);
}
2.一次冒泡过程使用递归代替for语句实现
/**
*
*冒泡排序
*
*使用递归方法实现
*/
private void sortByBubblinf(int[] paramInts) {
sortByBubbling(paramInts, 0, paramInts.length - 1);
}
/**
*
*冒泡排序递归实现的辅助方法
*paramInts:排序的数组对象
*index:对比到元素的下标
*minInex:序列最右边元素下标
*/
private void sortByBubbling(int[] paramInts, int index, int minIndex) {
if (minIndex == 0) {//左边没有可对比的相邻元素
return;
} else if (index == minIndex) {//没有可对比的元素
//重复1~5步骤
sortByBubbling(paramInts, 0, minIndex - 1);
} else if (paramInts[index] < paramInts[index + 1]) {
//小于相邻元素，与相邻元素交换
int temp = paramInts[index];
paramInts[index] = paramInts[index + 1];
paramInts[index + 1] = temp;
sortByBubbling(paramInts, index + 1, minIndex);
} else {
//大于等于相邻元素，重复步骤1~3
sortByBubbling(paramInts, index + 1, minIndex);
}
}
介绍完冒泡排序，讲解一下冒泡的时间复杂度
冒泡排序的时间复杂度为O(n^2)
时间复杂度
计算方法
1.一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
分析：随着模块n的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。
冒泡排序的时间复杂度计算过程：
冒泡排序是一种用时间换空间的排序方法，最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序。
在这种情况下，每一次比较都需要进行交换运算。
举个例子来说，一个数列 5 4 3 2 1 进行冒泡升序排列，
第一次大循环从第一个数（5）开始到倒数第二个数（2）结束，
比较过程：先比较5和4，4比5小，交换位置变成4 5 3 2 1；
比较5和3，3比5小，交换位置变成4 3 5 2 1
……
最后比较5和1，1比5小，交换位置变成4 3 2 1 5。
这时候共进行了4次比较交换运算，最后1个数变成了数列最大数。
第二次大循环从第一个数（4）开始到倒数第三个数（2）结束。进行3次比较交换运算。
……
所以总的比较次数为 4 + 3 + 2 + 1 = 10次对于n位的数列则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，这就得到了最大的比较次数而O(N^2)表示的是复杂度的数量级。
举个例子来说，如果n = 10000，那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2，相对10^8来说，10000小的可以忽略不计了，所以总计算次数约为0.5 * N2。用O(N2)就表示了其数量级（忽略前面系数0.5）。
2.选择排序
[90，78，65，43，20]
一次选择[20, 78, 65, 43, 90] 一次交换操作
二次选择:[20, 43, 65, 78, 90] 一次交换操作
三次选择:[20, 43, 65, 78, 90] 0次交换操作
四次选择:[20, 43, 65, 78, 90] 0次交换操作
共两次交换操作
1.查找序列中的最小元素与序列最左边元素交换
2.剩下的序列中，重复1步骤
3.直到序列的长度为1，完成排序
/**
*选择排序
*/
public void sortByCulling(int[] paramInts) {
sortByCulling(paramInts, 0);
}
/**
*选择排序辅助方法
*paramInts:排序的数组对象
*index:序列最左边元素的下标
*
*/
private void sortByCulling(int[] paramInts, int index) {
if (index == paramInts.length - 1) {
return;
}
//查询序列中的最小元素
int tempIndex = index;
int tempValue = paramInts[tempIndex];
//扫描序列中的元素
for (int i = index + 1; i < paramInts.length; i++) {
if ( paramInts[i] < tempValue) {//找到更小的元素
//记录下最小元素及下标
tempValue = paramInts[i];
tempIndex = i;
}
}
//扫描完序列
//判断最小元素是否是序列最左边的元素
if (tempIndex != index) {//不是
//交换元素
paramInts[tempIndex] = paramInts[index];
paramInts[index] = tempValue;
}
//调用函数本身
sortByCulling(paramInts, index + 1);
}
3.插入排序
[90，78，65，43，20]
一次插入
[78, 90, 65, 43, 20] 一次交换操作
二次插入
[78, 65, 90, 43, 20] 一次交换操作
[65, 78, 90, 43, 20] 一次交换操作
三次插入
[65, 78, 43, 90, 20] 一次交换操作
[65, 43, 78, 90, 20] 一次交换操作
[43, 65, 78, 90, 20] 一次交换操作
四次插入:
[43, 65, 78, 20, 90] 一次交换操作
[43, 65, 20, 78, 90] 一次交换操作
[43, 20, 65, 78, 90] 一次交换操作
[20, 43, 65, 78, 90] 一次交换操作
共十次交换操作
1.从第一个元素开始，该元素认定为已经被排序
2.取出下一个元素与已经排序的元素从后向前依次对比
3.如果取出的元素小与对比的元素，则交换
4.直到大于等于对比的元素则停止
5.重复2~4的步骤
6.直到没有可取出的元素为止
/**
*插入排序函数
*
*/
public void sortByInsertionCulling (int[] paramInts) {
sortByInsertionCulling(paramInts, 1);
}
/**
*插入排序辅助方法
*paramInts:排序数组对象
*index:取出元素的下标
*/
private void sortByInsertionCulling(int[] paramInts, int index) {
if (index == paramInts.length) {//取出元素的下标已经超出数组的长度，已经没有可取的元素
return;
}
//取出下标为index的元素
int tempValue = paramInts[index];
//记录取出元素的下标
int tempIndex = index;
//取出的元素与已经排序的元素从后向前依次对比
for (int i = index - 1; i >= 0; i--) {
if (tempValue < paramInts[i]) {//取出的元素小于当前元素
//与当前元素交换
paramInts[tempIndex] = paramInts[i];
paramInts[i] = tempValue;
tempIndex = i;
} else {//小于等于取出的元素
//停止对比
break;
}
}
//重复2~4步骤，调用函数本身
sortByInsertionCulling(paramInts, index + 1);
}
快速排序
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
[90，78，65，43，20]
一趟快速排序
[20, 78, 65, 43, 90] 一次交换操作
两趟快速排序
[20, 78, 65, 43, 90] 0次交换操作
三趟快速排序
[20, 43, 65, 78, 90] 一次交换操作
四趟快速排序
[20, 43, 65, 78, 90] 0次交换操作
共两次交换操作
参考文章一
参考文章二
