冒泡、插入、快速、选择排序的java实现
摘要：算法的好处什么的都不再赘述、单刀直入——直接贴出整理的几个常用的算法的基本描述、原理和java的实现过程。本篇是武功秘籍上部、下部还在酝酿中。
注：问题的引出都是对一系列可进行排序的数字进行排序。
一：冒泡排序
1、基本思想：
是一种基础的排序算法、用于入门。依次比较相邻的两个数、将小数放在前面、大数放在后面。即首先比较第一个与第二个数、将小数放前面、大数放后面、然后比较第二个数和第三个数、将小数放在前面、大数放在后面、如此继续、直至比较最后两个数、将小数放在前面、大数放在后面。重复上述过程、仍从第一对开始比较、将小数放在前面、大数放在后面。一直比较到前一趟比较得到的最大数前一对相邻数、并将小数放在前面、大数放在后面。如此下去直到完成排序。由于在排序过程中总是小数往前放、大数往后放、相当于气泡往上升、所以称作冒泡排序。
2、算法原理：
a）比较相邻元素、如果后者大、则交换他们的位置。
b）对每一对相邻的元素作同样的工作、从开始第一对、到最后一对。一次比较之后、最后一个值应该是最大的。
c）针对上面操作后的所有元素在进行同样的操作、但是下一次的比较不包含本次比较结束之后的最后一个元素。
d）持续对每次越来越少的元素重复上述步骤、直到没有任何一对数字需要比较。
注：最好是自己弄一个整形数组、按照上面的步骤在纸上实现排序、这样不但有个直观的认识、还会加深理解他的原理、步骤同时对下面代码的实现的理解也很有帮助。
3、java实现：
package com.chy.arithmetic;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] a = { 2, 3, 4, 1, 3, 4, 6, 7, 8, 9 };
System.out.println("before bubble sort： " + Arrays.toString(a));
System.out.println("after bubble sort： "
+ Arrays.toString(bubbleSort(a)));
}
private static int[] bubbleSort(int[] a) {
// the total compare times.
for (int j = 0; j < a.length; j++) {
// compare every group and every times it'll dismiss the last number.
for (int i = 0; i < a.length - j - 1; i++) {
// select one group which is composed of the current number and next to compare.
// if the next number is bigger than current, exchange them.
if (a[i] > a[i + 1]) {
int temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
return a;
}
}
二：插入排序
1、基本思想：
顾名思义、他是一种在已经拍好序的一个序列中插入数据、并且插入以后依然是排好序的。有点类似我们平时打牌一样、将新拿到手的牌插入他应该在的位置（当然、个人习惯和奇葩除外）。
插入排序算法把要排序的数组分成两个部分：第一部分包含了这个数组除了第一位的所有元素（当然也可以是最后一位元素）、而第二部分则只包含第一位元素。在第一位元素排序后（只有他一个、默认也就是排过序了）、依次取出另一部分的每个元素插入到第一部分中的适当位置。
2、算法原理：
a）从第一个元素开始、该元素可被认为已经排序
b）取出下一个元素、在已经排序的元素序列中从后向前扫描。
c） 如果该元素（已经排序的序列中的元素）大于新元素、则将该元素向后移一位。
d）重复c步骤、直到找到已排序的元素小于或者等于新元素的位置、或者扫描到已排序元素的最左侧。
e）将新元素插入到合适的位置。
i. 如果扫描到最左侧、则插入到最左侧
ii. 如果新元素小于或等于已排序元素值（称该元素）、则该元素后移一位、新元素插入当前位置
iii. 如果新元素大于所有已排序元素、则插入已排序元素最右侧。
f） 重复上述步骤、直到第二部分所有元素都完成插入操作。
3、java实现：
package com.chy.arithmetic;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr = { 10, 1, 41, 4, 5, 2, 6, 23, 7 };
System.out.println(Arrays.toString(insertSortByFirstElement(arr)));
System.out.println(Arrays.toString(insertSortByLastElement(arr)));
}
/**
* insert sort set the first element of an array as comparable number
*/
private static int[] insertSortByFirstElement(int[] a) {
for (int i = 1; i < a.length; i++) {
// the insert element's value
int insertValue = a[i];
// the index of sorted array's element;
int index = i - 1;
// to compare if there is some one is bigger than the new element.
while (index >= 0 && a[i] < a[index]) {
// move the current number to the next position(the original
// number of this position has also moved to the next position)
// in other words there are one more position than original.
a[index + 1] = a[index--];
}
// insert the value into the vacant position.
a[index + 1] = insertValue;
}
return a;
}
/**
* insert sort set the last element of an array as comparable number desc
*/
private static int[] insertSortByLastElement(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int insertValue = arr[arr.length - 1];
int index = arr.length - 2;
while (index >= 0 && arr[index] < insertValue) {
arr[index + 1] = arr[index--];
}
arr[index + 1] = insertValue;
}
return arr;
}
}
三：快速排序
1、简介：
快速排序是排序算法中效率最高的一种、它是利用递归原理、把数组无限制的费城两个部分、对每部分重复分割、排序。直到所有数据都拍好序为止。
2、基本思想：
快速排序是对冒泡排序的一种改进、他的基本思想是通过一次排序将要排序的数据分割成独立的两个部分、其中一个部分所有数据都比另一部分所有数据小、然后再按此方法对这两部分数据分别进行快速排序、整个排序过程是可以递归进行、以此达到整个数据变成有序序列。
3、算法原理：
a）设置两个变量i、j、排序开始的时候i=0、j=N-1（N为数组元素个数）。
b）以第一个数组元素作为关键数据、赋值给key。即key=a[0]。
c） 从j开始向前搜索、即由后向前搜索（j--）、找到第一个比key小的值a[j]、将a[j]赋给a[i]。
d）从i开始向后搜索、即由前向后搜索（i++）、找到第一个大于key的a[i]、将a[i]赋给a[j]。
e）重复c、d两步、直到i=j（c、d两步中，没找到符合条件的值，即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i，j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
4、java实现：
package com.chy.arithmetic;
import java.util.Arrays;
public class QuickSort {
private static int[] quickSort(int[] a, int start, int end) {
int i = start;
int j = end;
// if there is a element in a or the parameters is illegal.
if (start >= end) {
return a;
}
// if there are just two elements in a, just compare of them.
if ((end - start) == 1) {
if (a[start] > a[end]) {
switchNumber(a, start, end);
}
}
// while the sort doesn't end(i == j is the end condition of while loop)
while (i < j) {
// the key is a[i] before while loop
// Note: the key will be saved in a[j] when the while loop is end!
// look up the element which is bigger than key(a[i]) and the i<j by
// from end to start.
while (i < j && a[j] >= a[i]) {
// to make sure the big while loop will end and help us to find
// the element.
j--;
}
// exchange their position in a if we found it.
if (i < j) {
switchNumber(a, i, j);
}
// the key is a[j] before this while loop
// Note: the key will be saved in a[i] when the while loop is end!
// look up the element which is bigger than key(a[j]) and the i<j by
// from start to end.
while (i < j && a[i] < a[j]) {
// to make sure the big while loop will end and help us to find
// the element.
i++;
}
// exchange their position in a if we found it.
if (i < j) {
switchNumber(a, i, j);
}
// use the recursive algorithm to sort the first part of above
// result; the counter shaft is the key's index in a.
if (i - start > 1) {
quickSort(a, start, i - 1);
}
// use the recursive algorithm to sort the last part of above
// result; the counter shaft is the key's index in a.
if (end - i > 1) {
quickSort(a, i + 1, end);
}
}
return a;
}
private static void switchNumber(int[] a, int i, int j) {
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
public static void main(String[] args) {
int[] a = { 6, 8, 4, 7, 2, 3, 5, 1, 9 };
System.out.println(Arrays.toString(quickSort(a, 0, a.length - 1)));
}
}
四：选择排序
1、基本思想：
对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。
2、算法原理：
a）第一次循环：记录第一个数的下标
b）将第一个数的值与后面的值相比、如果比后面值大、则将下标值改为后面值所对应的下标。
c） 第一次循环结束后、如果下标值有改动、说明后面有比此数值小的元素、交换两者位置
d）重复上述操作、直到所有数值都已排序
3、java实现：
package com.chy.arithmetic;
import java.util.Arrays;
public class SelectSort {
private static int[] a = { 6, 8, 4, 7, 2, 3, 5, 1, 9 };
private static int[] selectSort(int[] a) {
for (int i = 0; i < a.length; i++) {
//register the current start index.
int lowIndex = i;
//from the next element to compare until the end of remanent elements.
for (int j = i + 1; j < a.length; j++) {
//if the next element's value is smaller than current.
if (a[j] < a[lowIndex]) {
//change the lowIndex's value to next element's index.
lowIndex = j;
}
}
//just exchange the value of two numbers when index has changed
if (lowIndex != i) {
int temp = a[i];
a[i] = a[lowIndex];
a[lowIndex] = temp;
}
}
return a;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(selectSort(a)));
}
}