公共函数
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
选择排序
// 选择排序，每次选取一个大的，或则小的
// 默认是升序，不稳定
// 本应两个版本(数组和链表），现在只做数组
public static void chooseSort(int[] array) {
int max = 0;
int index = 0;
for(int i = 0; i < array.length; i++ ) {
max = array[i];
for(int j = i+1; j < array.length; j++) {
if (array[j] > max) {
max = array[j];
index = j;
}
}
if (array[i] != max)
swap(array, i, index);
}
}
冒泡排序
static void bubble_sort(int[] unsorted)
{
for (int i = 0; i < unsorted.length; i++)
{
for (int j = i; j < unsorted.length; j++)
{
if (unsorted[i] > unsorted[j])
{
int temp = unsorted[i];
unsorted[i] = unsorted[j];
unsorted[j] = temp;
}
}
}
}
插入排序
// 插入排序，每次抽取一个，放在已排好序列中，稳定
public static void insertSort(int[] array) {
int temp = 0;
for(int i = 0; i < array.length; i++) {
temp = array[i];
for(int j= i-1; j >= 0; j--)
{
if(array[j] > array[i]) {
array[j+1] = array[j];
} else {
array[j+1] = temp;
break;
}
}
}
}
快速排序
// 快速排序：不稳定
// 根据文件，把控制当前排序进程的基准关键字放在关键位置上，左边都小于它， 右边都大于它
public static void quickSort(int[] array, int left, int right) {
if (left < right) {
int i = left;
int j = right + 1;
System.out.print("befor i = "+ i +" j is " + j +"\n");
int pivot = array[left];
System.out.print("pivot is " + pivot);
do {
do {
i++;
} while(i <= right && array[i] < pivot );
System.out.print("middle i = "+ i +" j is " + j +"\n");
do {
j--;
} while(array[j] > pivot && j >= left);
System.out.print("in do , i = "+ i +" j is " + j +"\n");
if(i < j) {
swap(array, i, j);
}
}while(i < j);
System.out.print("i = "+ i +" j is " + j +"\n");
printArray(array);
System.out.print("after swap");
swap(array,left,j);
printArray(array);
quickSort(array, left, j-1);
quickSort(array, j+1, right);
}
}
归并排序——迭代算法
// 1 2 5 7 2 4 3 ,每两两一组 合并
// 第一轮 12 57 24 3
// 第二轮 1257 234
// 第三轮1223457
// 归并从left到middle; middle+1到right的队列
public static void merge(int[] array, int[] sorted, int left, int middle, int right) {
int index = left;
int j = middle + 1;
while(left <= middle && j <= right) {
if (array[left] <= array[j]) {
sorted[index]= array[left];
left++;
}else {
sorted[index] = array[j];
j++;
}
index++;
}
while (left <= middle) {
sorted[index++] = array[left++];
}
while (j <= right) {
sorted[index++] = array[j++];
}
}
// 执行一轮归并
// merge_pass：sorted 表示存储新的数组，n表示list中的元素个数，length是一个subfile的长度
public static void merge_pass(int[] array, int[] sorted, int n, int length) {
// i <= n-2*length， 是防止后面不够
int i;
printArray(array);
for(i = 0; i <= n -2*length; i+= 2*length) {
merge(array, sorted, i, i+length-1, i+ 2*length-1);
System.out.println("i = " + i + "n = " + n);
printArray(sorted);
}
System.out.println(""+(i+length < n) +"i = " + i + "n = " + n);
if(i+length < n) {
// 还剩了一个多队列
merge(array, sorted, i, i+length-1, n-1);
}else {
for(int j = i; j < n; j++)
sorted[j] = array[j];
}
System.out.println("length "+ length);
printArray(sorted);
System.out.println("\n");
}
// 归并排序的入口
public static void merge_sort(int[] array, int n) {
int length =1;
int[] sorted = new int[array.length];
while(length < n) {
merge_pass(array, sorted, n, length);
length *=2;
merge_pass(sorted, array, n, length);
length *=2;
}
}
