原文链接 http://tblxdezhu.github.io/java/2016/09/16/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E5%B0%8F%E7%BB%93.html
注：以下为加速网络访问所做的原文缓存，经过重新格式化，可能存在格式方面的问题，或偶有遗漏信息，请以原文为准。
冒泡排序
原理主要是倒序比较
代码如下：
class Untitled {
public static void sortMaxMin(int array[]){
int i,j;
int len = array.length;
int temp;
//Boolean flag = true;
for (i = 0;i<len;i++) {//i<len&&flag
//flag = false;
for (j = len-1;j>i;j--) {
if (array[j-1]>array[j]) {
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
//flag = true;
}
}
}
}
public static void main(String[] args) {
int a[] = {2,1,3,4,5,6,7,8,9};
sortMaxMin(a);
for (int i = 0;i<a.length;i++) {
System.out.println(a[i]+" ");
}
}
}
算法复杂度：逆序情况下，需要比较1+2+...+(n-1),即复杂度为O(n2);
选择排序
基本流程：
外循环开始，将当前下标定义为最小值下标min，内循环开始比较，如果有小于当前最小值的关键字，将此关键字的下标赋值给min, 如果min不等于i，说明找到最小值，交换。
代码如下：
class Untitled {
public static void selectSort(int[] a){
int i,j;
int temp = 0;
int flag = 0;
for (i = 0;i<a.length;i++) {
temp = a[i];
flag = i;
for (j = i+1;j<a.length;j++) {
if (a[j]<temp) {
flag = j;
temp = a[j];
}
}
if (flag != i) {
a[flag] = a[i];
a[i] = temp;
}
}
}
public static void main(String[] args) {
int a[] = {4,6,1,2,11,9,3};
selectSort(a);
for (int i = 0;i<a.length;i++) {
System.out.println(a[i]+" ");
}
}
}
算法复杂度：依然为O(n2)
简化代码：
class Untitled {
public static void selectSort(int[] a){
int i,j;
int temp = 0;
int min = 0;
for (i = 0;i<a.length;i++) {
min = i;
for (j = i+1;j<a.length;j++) {
if (a[j]<a[min]) {
min = j;
}
}
if (min != i) {
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
public static void main(String[] args) {
int a[] = {6,1,4,2,9,8,3,5};
selectSort(a);
for (int i = 0;i<a.length;i++) {
System.out.println(a[i]+" ");
}
}
}
插入排序
代码如下：
class Untitled {
public static void charuSort(int a[]){
int i,j;
for (i = 1;i<a.length;i++) {
int temp = a[i];
j = i;
if (a[j-1] > temp) {
while (j>=1&&a[j-1]>temp) {
a[j] = a[j-1];
j--;
}
}
a[j] = temp;
}
}
public static void main(String[] args) {
int a[] = {6,1,4,2,9,8,3,5};
charuSort(a);
for (int i = 0;i<a.length;i++) {
System.out.println(a[i]+" ");
}
}
}
算法复杂度：同样的O(n2)，但是直接插入排序法比冒泡和简单选择排序的性能要好一些。