闲的无聊又拿起了大学的数据结构的书看起来 《数据结构（c语言版)》严蔚敏 吴伟民编著。
里面有几个排序算法，感觉挺好玩的，就想着写出来玩玩。
package test.sort;
/**
* @Title: TODO
* @Description: TODO
* @author:
* @date: 2014-8-10 上午11:20:43
*
*/
public class quickSort {
private static int datas[] = {23,42,12,45,56,63,24,41,32};
/**
* @Title: main
* @Description: TODO
* @param @param args
* @return void 返回类型
* @author
* @time 2014-8-10 上午11:20:43
* @throws
*/
public static void main(String[] args) {
// bubbleSort();
// quickSort(datas, 0, datas.length-1);
// selectSort(datas);
heapSort(datas);
for(int data : datas) {
System.out.print(data + " ");
}
}
//冒泡排序
public static void bubbleSort() {
for(int i = 0; i < datas.length-1; i++) {
for(int j = i+1; j < datas.length; j++) {
int num = 0;
if(datas[i] > datas[j]) {
num = datas[i];
datas[i] = datas[j];
datas[j] = num;
}
}
}
}
public static int partition(int datas[] , int low , int high) {
int pivotkey = datas[low];
while (low < high ) {
while(low < high && datas[high] >= pivotkey)
high--;
datas[low] = datas[high];
while (low < high && datas[low] <= pivotkey) {
low++;
}
datas[high] = datas[low];
}
datas[low] = pivotkey;
return low;
}
//快速排序算法
public static void quickSort(int datas[] , int low , int high) {
if(low < high) {
int pivotloc = partition(datas, low, high);
quickSort(datas, low, pivotloc-1);
quickSort(datas, pivotloc+1, high);
}
}
//选择排序
public static void selectSort(int datas[]) {
for(int i = 0; i < datas.length -1; i++) {
int j = selectMinKey(datas,i);
if(i != j) {
int num = datas[i];
datas[i] = datas[j];
datas[j] = num;
}
}
}
//找出数组中最小的值所在的位置
public static int selectMinKey(int datas[],int i) {
int minIndex = i;
int minData = datas[i];
for (int j = i+1; j < datas.length; j++) {
if (minData > datas[j]) {
minIndex = j;
minData = datas[j];
}
}
return minIndex;
}
//从第s个元素为根节点组成一个堆，也就是筛选
public static void heapAdjust(int datas[] ,int s, int m) {
int rc = datas[s];
for (int i = 2*s+1; i < m; i*=2) {
if(i < m-1 && datas[i] < datas[i+1])
i++;
if (rc >= datas[i]) {
break;
}
datas[s] = datas[i];
s = i;
}
datas[s] = rc;
}
//堆排序
public static void heapSort(int datas[]) {
for(int i = datas.length/2-1; i >= 0 ; i--)
heapAdjust(datas, i, datas.length);
for(int j = datas.length - 1; j > 0; j--) {
int num = datas[0];
datas[0] = datas[j];
datas[j] = num;
heapAdjust(datas, 0, j);
}
}
}