算法學習-常用排序

 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SuanFa
{
    public class SortMethod
    {
        //插入排序
        //把數B與其前面的數比較，如果B比其前面的數C小，
        //那么C到B之間的數都向后移一位，C所在的位置由B代替
        public bool InsertSort(int[] A, int n)
        {
            int sortData;
            for (int i = 1; i < n; i++)
            {
                sortData = A[i];
                for (int j = 0; j < i; j++)//循環(huán)一次只為插進一個數，循環(huán)n-1次即可
                {
                    if (A[j] > sortData)
                    {
                        for (int k = i; k > j; k--)//j-i之間的數向后移一位
                        {
                            A[k] = A[k - 1];
                        }
                        A[j] = sortData;
                        break;//break在這里很重要，如果沒有break，你看看A[j]=sortData;就執(zhí)行了i-k次，
                        // 排序后就會出現同一個數出現多次，當然有的數就去掉了。
                    }
                }
            }

            return true;
        }

        //冒泡排序
        public bool BubbleSort(int[] A, int n)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (A[j] > A[i])
                    {
                        int tmp = A[j];
                        A[j] = A[i];
                        A[i] = tmp;
                    }
                }
            }

            return true;
        }

        //選擇排序
        //把當前要排序的那個數與它后面的數進行比較，如果哪個數更小，就讓這個更小的輸入與后面的數進行比較，
        //一直比較下去，將當前要排序的數與更小的那個數交換
        public bool SelectSort(int[] A, int n)
        {
            for (int i = 0; i < n - 1; i++)
            {
                int k = i;
                for (int j = i + 1; j < n; j++)
                {
                    if (A[j] < A[k])
                    {
                        k = j;
                    }
                }

                if (k != i)
                {
                    int tmp = A[k];
                    A[k] = A[i];
                    A[i] = tmp;
                }
            }
            return true;
        }


        #region 合并排序
        /// <param name="A">被排序的數組</param>
        /// <param name="l">開始排序的下標</param>
        /// <param name="r">結束排序的下標</param>
        /// <param name="n">數組最后一個元素的下標</param>
        private void Merge(int[] A, int e, int r, int n)
        {
            int n1 = r - e ;
            int n2 = n - r+1;
            int[] e1 = new int[n1];
            int[] r1 = new int[n2];
            for (int t = 0; t < n1; t++)
            {
                e1[t] = A[e + t];
            }
            for (int t = 0; t < n2; t++)
            {
                r1[t] = A[r + t];
            }
            int i = 0, j = 0, k = e;
            while (i < n1 && j < n2)
            {
                if (e1[i] <= r1[j])
                {
                    A[k++] = e1[i++];
                }
                else
                {
                    A[k++] = r1[j++];
                }
            }
            while (i < n1)
            {
                A[k++] = e1[i++];
            }
            while (j < n2)
            {
                A[k++] = r1[j++];
            }
        }

        public void MergeSort(int[] A, int r, int n)
        {
            if (r < n)
            { 
               int p=(n+r)/2;
               MergeSort(A,r,p);
               MergeSort(A,p+1,n);
               Merge(A,r,p,n);
            }
        }
        #endregion

        //合并兩個數組,合并排序的思想就是合并兩個數組
        public int[] MergeTwo(int[] A, int[] B)
        {
            int n1 = A.Length;
            int n2 = B.Length;
            int[] C = new int[n1 + n2];
            int i=0,j =0,k=0;
            while (i < n1 && j < n2)
            {
                if (A[i] > B[j])
                {
                    C[k++] = B[j++];
                }
                else {
                    C[k++] = A[i++];
                }
            }
            while (i < n1)
            {
                C[k++] = A[i++];
            }

            while (j < n2)
            {
                C[k++] = B[j++];
            }
            return C;
        }

       //哈希算法

       //老實說這段代碼不是我寫的，哈希算法的確有點難懂，但我還是會他搞定
        public void HillSort(int[] list)
        {
            int inc;
            for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
             
            for (; inc > 0; inc /= 3)
            {
                for (int i = inc + 1; i <= list.Length; i += inc)
                {
                    int t = list[i - 1];
                    int j = i;
                    while ((j > inc) && (list[j - inc - 1] > t))
                    {
                        list[j - 1] = list[j - inc - 1];
                        j -= inc;
                    }
                    list[j - 1] = t;
                }
            }
        }   
 
    }
}