• C#中的排序

C#中的排序

• 选择排序

  选择排序是一种简单直观的排序算法，循环从待排序集合里取最大（最小）值，放到待排序集合的起始位（每次操作后，余下集合起始位是变化的）。

  时间复杂度为：O(n2)。稳定

  

        /// <summary>
        /// 选择排序
        /// </summary>
        private static void SelectSort()
        {
            for (int i = 0; i < tempArr.Length; i++)
            {
                int tarIndex = i;
                int tarValue = tempArr[i];
                for (int j = i + 1; j < tempArr.Length; j++)
                {
                    // > 从大到小；< 从小到大。
                    if (tempArr[j] > tarValue)
                    {
                        tarIndex = j;
                        tarValue = tempArr[j];
                    }
                }
  
                if (i != tarIndex)
                {
                    tempArr[tarIndex] = tempArr[i];
                    tempArr[i] = tarValue;
                }
            }
        }
  

• 冒泡排序

  比较相邻的两个元素，每次比较完毕最大（最小）的一个字跑到本轮的末尾。

  时间复杂度为：O(n2)。稳定

  

        /// <summary>
        /// 冒泡排序
        /// </summary>
        private static void BubbleSort()
        {
            int temp;
            for (int i = 0; i < tempArr.Length - 1; i++)
            {
                for (int j = i + 1; j < tempArr.Length; j++)
                {
                    // > 从大到小；< 从小到大。
                    if (tempArr[j] > tempArr[i])
                    {
                        temp = tempArr[j];
                        tempArr[j] = tempArr[i];
                        tempArr[i] = temp;
                    }
                }
            }
        }
  

• 快速排序

  通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

  时间复杂度为：O(n*log2n)。不稳定

  

        /// <summary>
        /// 快速排序
        /// </summary>
        private static void FastSort(int leftIndex,int rightIndex)
        {
            if (leftIndex >= rightIndex) return;
            int tempIndex = GetMiddleIndex(leftIndex, rightIndex);
            //递归处理
            FastSort(leftIndex, tempIndex - 1);
            FastSort(tempIndex + 1, rightIndex);
        }
        private static int GetMiddleIndex(int leftIndex, int rightIndex)
        {
            int middle = tempArr[leftIndex];
            int tempLeft = leftIndex;
            int tempRight = rightIndex;
            while (tempLeft < tempRight)
            {
                while (tempArr[tempRight] >= middle && tempLeft < tempRight) tempRight--;
                tempArr[tempLeft] = tempArr[tempRight];
                while (tempArr[tempLeft] <= middle && tempLeft < tempRight) tempLeft++;
                tempArr[tempRight] = tempArr[tempLeft];
            }
            tempArr[tempLeft] = middle;
            return tempLeft;
        }
  

• 插入排序

  把集合中第一个元素默认当成一个有序的集合，从第二个开始，依次读取后面元素插入到有序集合的相应位置上.（有序集合插入完成之后依然是一个有序集合）,注意：当插入到有序集合后，该位置后面元素依次向后移动一位。

  时间复杂度为：O(n2)。稳定

  

        /// <summary>
        /// 插入排序
        /// </summary>
        private static void InsertSort()
        {
            for (int i = 1; i < tempArr.Length; i++)
            {
                int insertVal = tempArr[i];
                int insertIndex = i - 1;
                while (insertIndex >= 0 && insertVal > tempArr[insertIndex])
                {
                    tempArr[insertIndex + 1] = tempArr[insertIndex];
                    insertIndex--;
                }
                tempArr[insertIndex + 1] = insertVal;
            }
        }
  

• 希尔排序

  排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

  把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

  时间复杂度为：O(n2)。不稳定。

  

        /// <summary>
        /// 希尔排序
        /// </summary>
        private static void ShellSort()
        {
            int gap = tempArr.Length / 2;
            while (1 <= gap)
            {
                for (int i = gap; i < tempArr.Length; i++)
                {
                    int j = 0;
                    int temp = tempArr[i];
  
                    for (j = i - gap; j >= 0 && temp < tempArr[j]; j = j - gap)
                    {
                        tempArr[j + gap] = tempArr[j];
                    }
                    tempArr[j + gap] = temp;
                }
  
                gap = gap / 2;
            }
        }