排序题

公共函数

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;
        }
    }