之前一篇练习数据结构中的二叉树-BinaryTree，本篇来点——排序算法，调调味，都是基本的排序算法中。
1. 冒泡排序
/**
* 冒泡排序
* @param arr
*/
public static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr, j, j+1);
}
}
}
}
2. 插入排序
/**
* 插入排序
* 要点：像扑克牌一样，小牌放在左边，插入的牌比左边的某张牌大（左边的牌已经排好大小），
* 该张牌后面的牌依次向右移动一个位置
* @param arr
*/
public static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i - 1;//要插入的牌和前面的所有牌比较
while(j >= 0 && arr[j] > temp){
arr[j+1] = arr[j];//向右移动一位
j--;
}
arr[j+1] = temp;//注意：j+1，因为循环中j--最后又执行一次了
}
}
3. 选择排序
/**
* 选择排序
* 每次选择一个最小（或最大）的数，拿走，再从剩下的数中重复选择最小（或最大）的数
* @param arr
*/
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
int min = i;//每次假定第一个数最小
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
swap(arr, i, min);
}
}
4. 快速排序
原理部分可以看这边文章，讲得很好，当时还真是坐在马桶上看的这篇文章，哈哈。
注意点：
-
如果基轴选的是左边的点，那么就应该从右边先开始遍历
-
左边是要找到一个比基轴大的数，对应程序中遍历左边时，注意要加上“=”，因为第一个数与基轴相同
/**
* 快速排序算法
* @param arr
* @param left
* @param right
*/
public static void quickSort(int[] arr, int left, int right) {
if (left > right) {
return;
}
int index = potrit(arr,left,right);
quickSort(arr, left, index - 1);
quickSort(arr, index + 1, right);
}
private static int potrit(int[] arr, int left, int right) {
int i = left;
int j = right;
int pivot = arr[left];
while(i != j){
while(arr[j] >= pivot && i < j){
j--;
}
//注意有 =，因为从第一个开始，所以要加等号，第一个与左边的pivot相等
while(arr[i] <= pivot && i < j){
i++;
}
if (i < j){
swap(arr, i, j);
}
}
arr[left] = arr[i];
arr[i] = pivot;
return i;
}
思考：为啥选择左边第一个数为基轴，就要从右边先开始遍历？
也就是两个while的顺序是不能改变的，假设对如下进行排序：
6--1--2--7--9
6在左，9在右 我们将6作为基轴。
假设从左边开始（与正确程序正好相反）于是 i 就会移动到现在的数字 7 那个位置停下来，而 j 原来在数字 9 那个位置 ，因为有 i<j 条件,于是，j 也会停留在数字 7 那个位置，于是问题来了。当你最后交换基数 6 与 7 时，就错了。问题在于当我们先从在边开始时，那么 i 所停留的那个位置肯定是大于基数6的，而在上述例子中，为了满足 i<j 于是 j也停留在 7 的位置,但最后交换回去的时候，7就到了左边，因为我们原本交换后数字 6 左边应该是全部小于6，右边全部大于 6，结果出现大于 6 的数字 7 就不行了。
所以，如果你选定左边的数为基轴，一定要从右边先开始，只有从右边才是要找到比基轴小的数，而左边是要找到比基轴大的数。
5. 交换
/**
* 交换数组中两个位置的数值
* @param arr
* @param i
* @param j
*/
public static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
总结
（1）这几种基本的排序算法，在实际中快速排序算法应用最多，效率最高，当然也相对更复杂，前面的三种也要理解，虽然可能用不到，但是作为练习，提高逻辑思维能力还是很有必要的。
（2）现在我有时还容易写错快速排序算法，所以多练习，多练习，多练习！
快速排序变形
当需要排序的数据很多时，可以将基轴选取为中间值，这样也能够提高效率。
/**
* 快速排序算法
* @param arr
* @param left
* @param right
*/
public static void quickSort(int[] arr, int left, int right) {
if (left > right) {
return;
}
int index = potrit(arr,left,right);
quickSort(arr, left, index - 1);
quickSort(arr, index + 1, right);
}
private static int potrit(int[] arr, int left, int right) {
int mid = left + (right-left)/2;
if (arr[mid] > arr[right]) {
swap(arr,mid,right);
}
if (arr[left] > arr[right]) {
swap(arr,left,right);
}
if (arr[mid] > arr[left]) {
swap(arr,mid,left);
}
int i = left;
int j = right;
int pivot = arr[left];
while(i != j){
while(arr[j] >= pivot && i < j){
j--;
}
//注意有 =，因为从第一个开始，所以要加等号，第一个与左边的pivot相等
while(arr[i] <= pivot && i < j){
i++;
}
if (i < j){
swap(arr, i, j);
}
}
arr[left] = arr[i];
arr[i] = pivot;
return i;
}
网友评论