快速排序&归并排序

快速排序和归并排序是非常常用的两种排序方式；
例如C# Array.Sort()就是快速排序的实现
java集合里Collections.sort()是归并排序及优化的归并排序（TimSort）
感兴趣的童鞋可以参考
C# Array.Sort 快速排序-源码分析
Collection.sort源码解析

以下是这两种排序方式的简单实现（Unity里实现的）：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;

public class Sort : MonoBehaviour {

    void Start () {
        int times = 0;
        List<int> array = new List<int> ();
        String nums = "";
        while(times < 20){
            int rand = UnityEngine.Random.Range (0, 100);
            array.Add (rand);
            nums += rand + " ";
            times++;
        }
        print ("origin:        " + nums);


        QuickSort (array,0,19);
        nums = "";
        foreach (int item in array) {
            nums += item + " ";
        }
        print ("QuickSort:  " + nums);


        MergeSort (array,0,19);
        nums = "";
        foreach (int item in array) {
            nums += item + " ";
        }
        print ("MergeSort: " + nums);
    }
    //  QuickSort
    void QuickSort(List <int>array,int low ,int high){
        if(low >= high){
            return;
        }
        int first = low;
        int last = high;
        int key = array [first];
        while(first < last){
            while(first <last && array[last] >= key){
                last--;
            }
            array[first] = array[last];
            while(first < last && array[first] <= key){
                first++;
            }
            array[last] = array[first];
        }
        array [first] = key;
        QuickSort (array,low,last);
        QuickSort (array,last + 1,high);
    }

    //Merge(归并)
    int[] extArray = new int[10000];
    void Merge(List<int> array,int low,int mid,int high){
        int i = low;
        int j = mid + 1;
        int index = 0;
        while(i < mid && j < high){

            if (array [i] <= array [j]) {
                extArray [index++] = array [i++];
            } else {
                extArray [index++] = array [j++];
            }
        }
        while(i < mid){
            extArray[index++] = array[i++];
        }
        while(j < high){
            extArray [index++] = array [j++];
        }
        for(int m = 0;m<index;m++){
            array [low++] = extArray [m];
        }
    }
    //MergeSort
    void MergeSort(List<int> array,int low,int high){

        if(low >= high){
            return;
        }
        int mid = (low + high) / 2;
        MergeSort (array,low,mid);
        MergeSort (array,mid + 1,high);
        Merge(array,low,mid,high);
    }

}

---

结果

完

顺便给大家推荐一首歌曲陈奕迅的《完》，相当消极的一首歌曲，适合充满正能量的人们听~