一.概述
排序算法在程序开发过程中可能用的比较少，但是也很有必要了解一下。我们相对更熟悉的应该是插入排序，选择排序，冒泡排序和快速排苏这四种排序算法。另外还有四中是对他们的优化算法，希尔排序是对选择排序的优化，堆排序是对选择排序的优化，还有两种就是归并排序和基数排序。
二.插入排序
原理：对于一个数组，我们取第一个数，依次加入第二个数,第三个数进行排序，直到最后一个数。加进来的数排序的过程就是要把它插入到一个有序的数列中，将它与有序数列最后一位开始往前比较找到一个比它更小或者相等的位置插入，这样加入的数也组成了一个新的有序数列，后面的数一样的道理。
过程：比如一个数组：
5，8，1，6，9，4，7，3
5，8，1，6，9，4，7，3（关注前两位，8插入进来）
1，5，8，6，9，4，7，3（关注前三位，1插入进来）
1，5，6，8，9，4，7，3（关注前四位，6插入进来）
1，5，6，8，9，4，7，3（关注前五位，9插入进来）
1，4，5，6，8，9，7，3（关注前六位，4插入进来）
1，4，5，6，7，8，9，3（关注前七位，7插入进来）
1，3，4，5，6，7，8，9（关注前八位，3插入进来）
代码：
/**
* 插入排序
*
* @param a
*/
public static void insertSort(int[] a) {
int len = a.length;
for (int i = 1; i < len; i++) {
int j = i;
while (j >= 0 && a[i] < a[j]) {//a[i]是要插入进来的数更小则a[j]后移
a[j + 1] = a[j];
j--;
}
a[j + 1] = a[i];//要插入进来的数a[i]大于a[j]，将a[i]值付给j+1位置
}
}
三.选择排序
原理：对于一个数组，遍历整个数组，将第二个数，第三个数直到最后一个数与第一个数比较得到最小的数和位置与第一个数替换，那么最小数就在第一位，以此类推，剩下的数最小数放到第二位，第三位...直到最后两位把更小的数放到倒数第二个位置完成排序。
过程：比如一个数组：
5，8，1，6，9，4，7，3
1，8，5，6，9，4，7，3（关注最小数1和第一位5替换了）
1，3，5，6，9，4，7，8（关注最小数3和第二位8替换了）
1，3，4，6，9，5，7，8（关注最小数4和第三位5替换了）
1，3，4，5，9，6，7，8（关注最小数5和第四位6替换了）
1，3，4，5，6，9，7，8（关注最小数6和第五位9替换了）
1，3，4，5，6，7，9，8（关注最小数7和第六位9替换了）
1，3，4，5，6，7，8，9（关注最小数8和第七位9替换了）
代码：
/**
* 选择排序
*
* @param a
*/
public void selectSort(int[] a) {
int len = a.length;
for (int i = 0; i < len; i++) {//循环次数
int value = a[i];
int position = i;
for (int j = i + 1; j < len; j++) {//找到最小的值和位置
if (a[j] < value) {
value = a[j];
position = j;
}
}
a[position] = a[i];//进行交换
a[i] = value;
}
}
四.冒泡排序
原理：对于一个数组，遍历整个数组，两个两个比较，把更大的数往后挪，如果前一个数比后一个数大，直接进行替换，这样最大的数就会放在最后面，再以此类推，把第二大的数放到倒数第二个位置，直到将倒数第二大的数放大第二个位置排序就结束了。
过程：比如一个数组：
5，8，1，6，9，4，7，3
第一轮：
5，8，1，6，9，4，7，3
5，1，8，6，9，4，7，3（8和1比较替换）
5，1，6，8，9，4，7，3（8和6比较替换）
5，1，6，8，9，4，7，3（8和9比较不变）
5，1，6，8，4，9，7，3（9和4比较替换）
5，1，6，8，4，7，9，3（9和7比较替换）
5，1，6，8，4，7，3，9（9和3比较替换，第一轮结束，9到了最后面）
第二轮，同样的道理得到：
1，5，6，4，7，3，8，9（8也安排上了）
第三轮：
1，5，4，6，3，7，8，9（7也安排上了）
第四轮：
1，4，5，3，6，7，8，9（6也安排上了）
第五轮：
1，4，3，5，6，7，8，9（5也安排上了）
第六轮：
1，3，4，5，6，7，8，9（4也安排上了）
第七轮：
1，3，4，5，6，7，8，9（3也安排上了）
代码：
/**
* 冒泡排序
* @param a
*/
public void bubbleSort(int []a){
int len=a.length;
for(int i=0;i<len;i++){
for(int j=0;j<len-i-1;j++){//注意最后面那些是已排好序的不需要在比较
if(a[j]>a[j+1]){
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
五.快速排序
原理：对于一个数组，选取第一个数作为参照值，设定两个下标作为向中间夹逼，一个low从1开始，一个high从最后一位也就是length-1开始，开始从high下标与参考值比较，如果比参考值大位置不变，high下标减一直到比参考值小则对调并且high下标减一方便下一次比较，此时用low下标与参考值比较，如果比参考值小位置不变，low值加一继续比较直到比参考值大则对调并且low下标加一方便下一次比较，此时再换到high下表比较，以此类推直到low和high夹逼相逢就会实现参考值左侧都是小于参考值，参考值的右侧都是大于参考值，然后分别对参考值的左侧和右侧使用同样方法夹逼排序。
过程：比如一个数组：
5，8，1，6，9，4，7，3
第一轮：
5，8，1，6，9，4，7，3
3，8，1，6，9，4，7，5（用3和5比较对调，使用high下标7）
3，5，1，6，9，4，7，8（用8和5比较对调，使用low下标1）
3，5，1，6，9，4，7，8（用7和5比较不变，使用high下标6）
3，4，1，6，9，5，7，8（用4和5比较对调，使用high下标5）
3，4，1，6，9，5，7，8（用1和5比较不变，使用low下标2）
3，4，1，5，9，6，7，8（用6和5比较对调，使用low下标3）
3，4，1，5，9，6，7，8（用9和5比较不变，使用high下标4，此时low和high相逢了，结束，观察5的两侧）
第二轮，以此类推：
1，3，4，5，8，6，7，9（观察3和9两侧）
第三轮：
1，3，4，5，7，6，8，9（观察8的两侧）
第四轮：
1，3，4，5，6，7，8，9（观察7的两侧）
代码：
/**
* 快速排序
*
* @param a
* @param low
* @param high
*/
public static void quickSort(int[] a, int low, int high) {
if (low < high) {
int baseNum = a[low];//选基准值
int midNum;//记录中间值
int i = low;
int j = high;
do {
while ((a[i] < baseNum) && i < high) {
i++;
}
while ((a[j] > baseNum) && j > low) {
j--;
}
if (i <= j) {
midNum = a[i];
a[i] = a[j];
a[j] = midNum;
i++;
j--;
}
} while (i <= j);
if (low < j) {
quickSort(a, low, j);
}
if (high > i) {
quickSort(a, i, high);
}
}
}
五.总结
以上就是关于Java常用的排序算法的相关知识点，如有不足或者错误的地方请在下方指正。
网友评论