排序算法

  1 /*
  2  * SortUtil.cpp
  3  *
  4  *  Created on: 2015年4月21日
  5  *      Author: 
  6  */
  7 
  8 #include "SortUtil.h"
  9 
 10 #include <string.h>
 11 #include <iostream>
 12 using namespace std;
 13 
 14 SortUtil::SortUtil()
 15 {
 16     // TODO Auto-generated constructor stub
 17 
 18 }
 19 
 20 SortUtil::~SortUtil()
 21 {
 22     // TODO Auto-generated destructor stub
 23 }
 24 
 25 void SortUtil::merge_sort( int* array, size_t start, size_t end )
 26 {
 27     if(start<end){
 28         size_t middle = (start+end+1)/2;//注意+1
 29         merge_sort(array, start, middle-1);
 30         merge_sort(array, middle, end);
 31         merge(array, start, middle, end);
 32     }
 33 }
 34 
 35 void SortUtil::merge( int* array, size_t start, size_t middle, size_t end )
 36 {
 37     if(!(start<middle && middle<=end)){
 38         return;
 39     }
 40     size_t left_size = middle-start;
 41     size_t right_size = end-middle+1;
 42     //--------将左右两半数组分别拷贝到left和right中
 43     int left[left_size];
 44     int right[right_size];
 45     memcpy(left, array+start, left_size*sizeof(int));
 46     memcpy(right, array+middle, right_size*sizeof(int));
 47 /*    for(size_t i=0; i<left_size; ++i){
 48         left[i] = array[start+i];
 49     }
 50     for(size_t i=0; i<right_size; ++i){
 51         right[i] = array[middle+i];
 52     }*/
 53     size_t index = start;//array的index
 54     size_t left_index = 0;
 55     size_t right_index = 0;
 56     while(left_index<left_size && right_index<right_size){
 57         if(left[left_index] <= right[right_index]){
 58             array[index++] = left[left_index++];
 59         }else{
 60             array[index++] = right[right_index++];
 61         }
 62     }
 63     if(left_index >= left_size){
 64         while(right_index < right_size){
 65             array[index++] = right[right_index++];
 66         }
 67     }else{
 68         while(left_index < left_size){
 69             array[index++] = left[left_index++];
 70         }
 71     }
 72 }
 73 
 74 void SortUtil::quick_sort( int* array, size_t start, size_t end )
 75 {
 76     if(start >= end){
 77         return;
 78     }
 79     size_t middle = partition(array, start, end);
 80     if(middle>0){//由于middle为size_t类型的，当middle为0，则减1会出问题
 81         quick_sort(array, start, middle-1);
 82     }
 83     quick_sort(array, middle+1, end);
 84 }
 85 
 86 /**
 87  * 调用程序必须保证start<end
 88  */
 89 size_t SortUtil::partition( int* array, size_t start, size_t end )
 90 {
 91     if(start == end){
 92         return start;
 93     }
 94     if(start > end){
 95         cout<<"error: start > end"<<endl;
 96         return end;
 97     }
 98     int partition_value = array[start];
 99     size_t index = start+1;//迭代用的索引
100     size_t less_index = start;//始终指向小于等于partition_value的最靠右的元素
101     for(; index<=end; ++index){
102         if(array[index] <= partition_value){
103             ++less_index;
104             if(less_index != index){
105                 swap(array, less_index, index);
106             }
107         }
108     }
109     swap(array, less_index, start);
110     return less_index;
111 }
112 
113 void SortUtil::swap( int* array,const size_t l, const size_t r )
114 {
115     if(l == r){
116         return;
117     }
118     int tmp = array[l];
119     array[l] = array[r];
120     array[r] = tmp;
121 }

package algorithm;

public class SortUtil {

    public static void mergeSort(int[]array, int start, int end){
        if(start >= end){
            return;
        }
        int middle = (start+end+1)/2;
        mergeSort(array, start, middle-1);
        mergeSort(array, middle, end);
        merge(array, start, middle, end);
    }
    public static void merge(int[]array, int start, int middle, int end){
        if(!(start<middle && middle<=end)){
            return;
        }
        int leftSize = middle-start;
        int rightSize = end-middle+1;
        int[] leftArray = new int[leftSize];
        int[] rightArray = new int[rightSize];
        for(int i=0; i<leftSize; ++i){
            leftArray[i] = array[start+i];
        }
        for(int i=0; i<rightSize; ++i){
            rightArray[i] = array[middle+i];
        }
        int index = start;
        int leftIndex = 0; 
        int rightIndex = 0;
        while(leftIndex<leftSize && rightIndex<rightSize){
            if(leftArray[leftIndex] <= rightArray[rightIndex]){
                array[index++] = leftArray[leftIndex++];
            }else{
                array[index++] = rightArray[rightIndex++];
            }
        }
        if(leftIndex == leftSize){
            while(rightIndex<rightSize){
                array[index++] = rightArray[rightIndex++];
            }
        }else{
            while(leftIndex<leftSize){
                array[index++] = leftArray[leftIndex++];
            }
        }
    }
    
    //----------------------------
    public static void quickSort(int[]array, int start, int end){
        if(start>=end){
            return;
        }
        int middle = partition(array, start, end);
        quickSort(array, start, middle-1);
        quickSort(array, middle+1, end);
    }
    public static int partition(int[]array, int start, int end){
        if(start == end){
            return start;
        }
        if(start > end){
            System.out.println("error!");
            return end;
        }
        int partitionValue = array[start];
        int lessIndex = start;
        for(int index = start+1; index<=end; ++index){
            if(array[index]<=partitionValue){
                lessIndex++;
                if(lessIndex != index){
                    swap(array, lessIndex, index);
                }
            }
        }
        swap(array, start, lessIndex);
        return lessIndex;
    }
    public static void swap(int[]array, int l, int r){
        if(l == r){
            return;
        }
        int tmp = array[l];
        array[l] = array[r];
        array[r] = tmp;
    }
    
    public static void main(String[] args){
        
        int[]array = {10,2,8,7,6,5,9,1,3,4};
//        mergeSort(array, 0, array.length-1);
        quickSort(array, 0, array.length-1);
        for(int i:array){
            System.out.print(i+" ");
        }
    }
}