之前一篇练习数据结构中的二叉树-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;
}