轉(zhuǎn)載：http://blog.csdn.net/pzhtpf/article/details/7559943
一、簡單選擇排序
基本思想：
在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換；
然后在剩下的數(shù)當中再找最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。
實例：
這里寫圖片描述
Java實現(xiàn)：
package com.tao.algorithm;
/**
* Created by michael on 17-8-13.
*/
public class 簡單選擇排序 {
public static void main(String[] args) {
int[] a = new int[] {49,38,65,97,76,13,27,49,78,34,12,64,5,4,
62,99,98,54,56,17,18,23,34,15,35,25,53,51};
System.out.println("排序前：");
print(a);
//冒泡排序
selectSort(a);
System.out.println("排序后：");
print(a);
}
/**
* 簡單選擇排序
* @param array
*/
public static void selectSort(int[] array) {
int length = array.length;
int temp, minIndex;
for(int i = 0; i < length; i++) {
minIndex = i;
for(int j = i+1; j < length; j++) {
if(array[j] < array[minIndex]) {
//找到最小值的索引
minIndex = j;
}
}
temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
/**
* 打印函數(shù)
* @param array
*/
public static void print(int[] array) {
for (int a : array) {
System.out.print(a + " ");
}
System.out.println();
}
}
二、直接插入排序
基本思想：
在要排序的一組數(shù)中，假設前面(n-1) [n>=2] 個數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個數(shù)插到前面的有序數(shù)中，使得這n個數(shù)也是排好順序的。如此反復循環(huán)，直到全部排好順序。
實例：
這里寫圖片描述
Java實現(xiàn)：
package com.tao.algorithm;
/**
* Created by michael on 17-8-13.
*/
public class 直接插入排序 {
public static void main(String[] args) {
int[] a = new int[] {49,38,65,97,76,13,27,49,78,34,12,64,5,4,
62,99,98,54,56,17,18,23,34,15,35,25,53,51};
System.out.println("排序前：");
print(a);
//直接插入排序
insertSort(a);
System.out.println("排序后：");
print(a);
}
/**
* 直接插入排序
* @param array
*/
public static void insertSort(int[] array) {
int length = array.length;
int temp, j;
for(int i = 1; i < length; i++) {
temp = array[i];
for(j = i; j > 0 && temp < array[j-1]; j--) {
array[j] = array[j-1];
}
array[j] = temp;
}
}
/**
* 打印函數(shù)
* @param array
*/
public static void print(int[] array) {
for (int a : array) {
System.out.print(a + " ");
}
System.out.println();
}
}
三、歸并排序
基本思想：
歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
實例：
這里寫圖片描述
Java實現(xiàn)：
package com.tao.algorithm;
import jdk.nashorn.internal.runtime.Context;
/**
* Created by michael on 17-8-13.
*/
public class 歸并排序 {
public static void main(String[] args) {
int[] a = new int[] {49,38,65,97,76,13,27,49,78,34,12,64,5,4,
62,99,98,54,56,17,18,23,34,15,35,25,53,51};
System.out.println("排序前：");
print(a);
//歸并排序
mergeSort(a, 0, a.length-1);
System.out.println("排序后：");
print(a);
}
/**
* 歸并排序
* @param array
* @param start
* @param end
*/
public static void mergeSort(int[] array, int start, int end) {
if(start < end) {
//找出中間位置
int mid = (start+end)/2;
//分別對左右進行歸并排序
mergeSort(array, start, mid);
mergeSort(array, mid+1, end);
//合并
merge(array, start, mid, end);
}
}
/**
* 合并,合并的時候，左右兩邊是排好序的序列
* @param array
* @param start
* @param mid
* @param end
*/
public static void merge(int[] array, int start, int mid, int end) {
//暫存中間結(jié)果的數(shù)組
int[] tempArray = new int[array.length];
int pLeft = start; //左邊序列的游標
int pRight = mid+1; //右邊序列的游標
int pTemp = start; //臨時數(shù)組的游標
while(pLeft <= mid && pRight <= end) {
//每次從兩個序列中取出最小的放入臨時數(shù)組
if(array[pLeft] <= array[pRight]) {
tempArray[pTemp++] = array[pLeft++];
} else {
tempArray[pTemp++] = array[pRight++];
}
}
//剩余部分以此放入中間數(shù)組
while(pLeft <= mid) {
tempArray[pTemp++] = array[pLeft++];
}
while(pRight <= end) {
tempArray[pTemp++] = array[pRight++];
}
//將臨時數(shù)組的內(nèi)容復制回原數(shù)組
pTemp = start;
while(pTemp <= end) {
array[pTemp] = tempArray[pTemp++];
}
}
/**
* 打印函數(shù)
* @param array
*/
public static void print(int[] array) {
for (int a : array) {
System.out.print(a + " ");
}
System.out.println();
}
}
