排序

介绍
快排
- 算法实现
- 相关题目
归并排序
- 算法实现
- 相关题目
堆排序
- 算法实现
- 相关题目

介绍

排序中需要熟练掌握时间复杂度为O(nlog(n))的三种排序实现，快排，归并排序，堆排序。

快排

算法实现

public void quickSort(int[] array,int start,int end){
    if(start<=end){
        return;
    }
    int pos = partition(array,0,array.length-1);
    quickSort(array,start,pos-1);
    quickSort(array, pos+1, end);
}

//快排的partition基本实现
private int partition(int[] array, int start, int end) {
    // 保存小于最后一个数的位置
    int small = start - 1;
    for (int i = start; i < end; i++) {
        // 与最后一个元素比较
        if (array[i] < array[end]) {
            small++;
            if (i != small) {
                swap(array, i, small);
            }
        }
    }
    small++;
    swap(array, small, end);
    return small;
}

private void swap(int[] array, int i, int j) {
    int temp = array[j];
    array[j] = array[i];
    array[i] = temp;
}

@Test
public void quickSort(){
    int[] array = new int[] { 1,4,2,3,5,6 };
    quickSort(array,0,array.length-1);
}

归并排序

空间复杂对为O(n)。

算法实现

private void mergeSort(int[] nums, int start, int end, int[] copy) {
    if (start == end) {
        return;
    }
    int mid = (end - start) / 2 + start;
    mergeSort(nums, start, mid, copy);
    mergeSort(nums, mid + 1, end, copy);
    merge(nums, start, mid, end, copy);
}

public void merge(int[] nums, int start, int mid, int end, int[] copy) {
    int count = start;
    int p1, p2;
    // merge两个有序的序列
    for (p1 = start, p2 = mid + 1; p1 <= mid && p2 <= end;) {
        if (nums[p1] <= nums[p2]) {
            copy[count] = nums[p1++];
        } else {
            copy[count] = nums[p2++];
        }
        count++;
    }
    for (int i = p1; i <= mid; i++) {
        copy[count++] = nums[i];
    }
    for (int i = p2; i <= end; i++) {
        copy[count++] = nums[i];
    }
    // 将排序好的序列复制回原数组
    for (int i = start; i <= end; i++) {
        nums[i] = copy[i];
    }
}

@Test
public void mergeSort() {
    int[] nums = new int[] { 2, 5, 3, 1, 8, 4, 7 };
    mergeSort(nums, 0, nums.length - 1, new int[nums.length]);
}

相关题目

剑指offer36题：数组中逆序对

 private int number;
 public int inversePairs(int[] array) {
     if (array == null || array.length < 2) {
         return 0;
     }
     int len = array.length;
     mergeSort(array, 0, len - 1, new int[len]);
     return number;
 }

 private void mergeSort(int[] nums, int start, int end, int[] copy) {
     if (start == end) {
         return;
     }
     int mid = (end - start) / 2 + start;
     mergeSort(nums, start, mid, copy);
     mergeSort(nums, mid + 1, end, copy);
     merge(nums, start, mid, end, copy);
 }

 public void merge(int[] nums, int start, int mid, int end, int[] copy) {
     int count = start;
     int p1, p2;
     // merge两个有序的序列
     for (p1 = start, p2 = mid + 1; p1 <= mid && p2 <= end;) {
         if (nums[p1] <= nums[p2]) {
             copy[count] = nums[p1++];
         } else {
             copy[count] = nums[p2++];
             number+=(mid-p1+1);//记录逆序对
         }
         count++;
     }
     for (int i = p1; i <= mid; i++) {
         copy[count++] = nums[i];
     }
     for (int i = p2; i <= end; i++) {
         copy[count++] = nums[i];
     }
     // 将排序好的序列复制回原数组
     for (int i = start; i <= end; i++) {
         nums[i] = copy[i];
     }
 }

堆排序

堆排序有两个过程：

初始堆的构造（O(n)）；
堆的调整O(log(n))。

算法实现

public void heapSort(int[] nums){
    if(nums==null|nums.length==0){
        return;
    }
    //构造初始化堆
    initConstruct(nums);
    //调整堆
    for(int i=nums.length-1;i>0;i--){
        swap(nums,0,i);
        adjust(nums,i);            
    }
    System.out.println(nums);
}

//调整堆
private void adjust(int[] nums,int len) {
    adjust(nums,len,0);    
}

//构造初始化堆
private void initConstruct(int[] nums) {
    int len = nums.length;
    int notLeaf=(len-2)/2;
    for(int i=notLeaf;i>=0;i--){            
        adjust(nums,len,i);        
    }
}

//构造堆
private void adjust(int[] nums, int len, int start) {
    int left = start*2+1;
    int right = start*2+2;
    int minIndex=start;
    if(left<len&&nums[left]>nums[minIndex]){
        minIndex=left;
    }
    if(right<len&&nums[right]>nums[minIndex]){
        minIndex=right;
    }
    if(minIndex!=start){
        swap(nums,start,minIndex);
        adjust(nums,len,minIndex);
    }
}

//数组元素交换
private void swap(int[] nums, int i, int j) {
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;        
}