JAVAソートアルゴリズム
import java.util.Random;
/**
*
*
* ：
* 1. （ 、 、 ）；
* 2. （ 、 ）；
* 3. （ 、 ）；
* 4. ；
* 5. 。
*
* ：
* (1) n ( n≤50)， 。
* ， ； ， 。
* (2) ( )， 、 ；
* (3) n ， O(nlgn) ： 、 。
*
*/
public class SortTest {
/**
*
* @return
*/
public int[] createArray() {
Random random = new Random();
int[] array = new int[10];
for (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100) - random.nextInt(100);// ，
}
System.out.println("========== ==========");
printArray(array);
return array;
}
/**
*
* @param source
*/
public void printArray(int[] data) {
for (int i : data) {
System.out.print(i + " ");
}
System.out.println();
}
/**
*
* @param data
* @param x
* @param y
*/
private void swap(int[] data, int x, int y) {
int temp = data[x];
data[x] = data[y];
data[y] = temp;
}
/**
* ----
* ： ， ， （ ）， 。
* ： O(n^2),n^2/2； O(n^2),n^2/4
*
* @param data
* @param sortType
* @return
*/
public void bubbleSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // ，
//
for (int i = 1; i < data.length; i++) {
// ，
for (int j = 0; j < data.length - i; j++) {
if (data[j] > data[j + 1]) {
//
swap(data, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { // ，
//
for (int i = 1; i < data.length; i++) {
// ，
for (int j = 0; j < data.length - i; j++) {
if (data[j] < data[j + 1]) {
//
swap(data, j, j + 1);
}
}
}
} else {
System.out.println(" ！");
}
printArray(data);//
}
/**
* ----
* ： （ ） ， ， 。
* ： O(n^2),n^2/2
* O(n),n
* ， CPU CUP ， 。
* N ， CPU ， ， 。
*
* @param data
* @param sortType
* @return
*/
public void selectSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // ，
int index;
for (int i = 1; i < data.length; i++) {
index = 0;
for (int j = 1; j <= data.length - i; j++) {
if (data[j] > data[index]) {
index = j;
}
}
// data.length-i index( )
swap(data, data.length - i, index);
}
} else if (sortType.equals("desc")) { // ，
int index;
for (int i = 1; i < data.length; i++) {
index = 0;
for (int j = 1; j <= data.length - i; j++) {
if (data[j] < data[index]) {
index = j;
}
}
// data.length-i index( )
swap(data, data.length - i, index);
}
} else {
System.out.println(" ！");
}
printArray(data);//
}
/**
*
* ： （ ） , 1 。
* ： O(n^2),n^2/4
* O(n),n^2/4
* ， CPU ， ， 。
*
* @param data
* @param sortType
*/
public void insertSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // ，
//
for (int i = 1; i < data.length; i++) {
// i+1
for (int j = 0; j < i; j++) {
if (data[j] > data[i]) {
// j i
swap(data, i, j);
}
}
}
} else if (sortType.equals("desc")) { // ，
//
for (int i = 1; i < data.length; i++) {
// i+1
for (int j = 0; j < i; j++) {
if (data[j] < data[i]) {
// j i
swap(data, i, j);
}
}
}
} else {
System.out.println(" ！");
}
printArray(data);//
}
/**
*
* @param data
*/
public void reverse(int[] data) {
int length = data.length;
int temp = 0;//
for (int i = 0; i < length / 2; i++) {
temp = data[i];
data[i] = data[length - 1 - i];
data[length - 1 - i] = temp;
}
printArray(data);//
}
/**
*
* （Divide and conquer） （list） （sub-lists）。
* ：
* 1. ， " "（pivot），
* 2. ， ， （ ）。 ， 。 （partition） 。
* 3. （recursive） 。
* ， ， 。 ， ， （iteration） ， 。
* @param data
* @param low
* @param high
* @see SortTest#qsort(int[], int, int)
* @see SortTest#qsort_desc(int[], int, int)
*/
public void quickSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // ，
qsort_asc(data, 0, data.length - 1);
} else if (sortType.equals("desc")) { // ，
qsort_desc(data, 0, data.length - 1);
} else {
System.out.println(" ！");
}
}
/**
* ，
* @param data
* @param low
* @param high
*/
private void qsort_asc(int data[], int low, int high) {
int i, j, x;
if (low < high) { //
i = low;
j = high;
x = data[i];
while (i < j) {
while (i < j && data[j] > x) {
j--; // x
}
if (i < j) {
data[i] = data[j];
i++;
}
while (i < j && data[i] < x) {
i++; // x
}
if (i < j) {
data[j] = data[i];
j--;
}
}
data[i] = x;
qsort_asc(data, low, i - 1);
qsort_asc(data, i + 1, high);
}
}
/**
* ，
* @param data
* @param low
* @param high
*/
private void qsort_desc(int data[], int low, int high) {
int i, j, x;
if (low < high) { //
i = low;
j = high;
x = data[i];
while (i < j) {
while (i < j && data[j] < x) {
j--; // x
}
if (i < j) {
data[i] = data[j];
i++;
}
while (i < j && data[i] > x) {
i++; // x
}
if (i < j) {
data[j] = data[i];
j--;
}
}
data[i] = x;
qsort_desc(data, low, i - 1);
qsort_desc(data, i + 1, high);
}
}
/**
* ( )
*
*@paramdataset
*@paramdata
*@parambeginIndex
*@paramendIndex
*@returnindex
*/
public int binarySearch(int[] dataset, int data, int beginIndex,
int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; // mid = (low + high) / 2，
if (data < dataset[beginIndex] || data > dataset[endIndex]
|| beginIndex > endIndex)
return -1;
if (data < dataset[midIndex]) {
return binarySearch(dataset, data, beginIndex, midIndex - 1);
} else if (data > dataset[midIndex]) {
return binarySearch(dataset, data, midIndex + 1, endIndex);
} else {
return midIndex;
}
}
/**
* ( )
*
*@paramdataset
*@paramdata
*@returnindex
*/
public int binarySearch(int[] dataset, int data) {
int beginIndex = 0;
int endIndex = dataset.length - 1;
int midIndex = -1;
if (data < dataset[beginIndex] || data > dataset[endIndex]
|| beginIndex > endIndex)
return -1;
while (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; // midIndex = (beginIndex + endIndex) / 2，
if (data < dataset[midIndex]) {
endIndex = midIndex - 1;
} else if (data > dataset[midIndex]) {
beginIndex = midIndex + 1;
} else {
return midIndex;
}
}
return -1;
}
public static void main(String[] args) {
SortTest sortTest = new SortTest();
int[] array = sortTest.createArray();
System.out.println("========== ( )==========");
sortTest.bubbleSort(array, "asc");
System.out.println("========== ( )==========");
sortTest.bubbleSort(array, "desc");
array = sortTest.createArray();
System.out.println("========== ==========");
sortTest.reverse(array);
array = sortTest.createArray();
System.out.println("========== ( )==========");
sortTest.selectSort(array, "asc");
System.out.println("========== ( )==========");
sortTest.selectSort(array, "desc");
array = sortTest.createArray();
System.out.println("========== ( )==========");
sortTest.insertSort(array, "asc");
System.out.println("========== ( )==========");
sortTest.insertSort(array, "desc");
array = sortTest.createArray();
System.out.println("========== ( )==========");
sortTest.quickSort(array, "asc");
sortTest.printArray(array);
System.out.println("========== ( )==========");
sortTest.quickSort(array, "desc");
sortTest.printArray(array);
System.out.println("========== ==========");
System.out.println(" " + sortTest.binarySearch(array, 74)
+ " 。（ 0 ）");
}
}転載先: http://blog.csdn.net/zuoluoboy/article/details/4123943