范少华的技术学习 Unity Coder

C#算法学习

2018-07-07
FSH
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;
              }
          }
    

下一篇 我的博客

Comments

Content