C# 클래식 정렬 알고리즘의 그래픽 코드에 대한 자세한 설명(2부)

이 글에서는 C#의 7가지 고전 정렬 알고리즘인 직접 삽입 정렬, 힐 정렬, 병합 정렬 시리즈의 다음 부분을 주로 소개합니다. 🎜>

오늘은 마지막 세 가지 정렬인 직접 삽입 정렬, 힐 정렬, 병합 정렬에 대해 말씀드리겠습니다.

직접 삽입 정렬:

이러한 정렬은 실제로 매우 이해하기 쉽습니다. 매우 현실적인 예는 우리가 무작위로 카드를 잡을 때입니다. 포커 카드를 크기별로 분류해야 하는데 30초가 지나면 포커 카드가 3, 5, 4개로 분류됩니다. 와... 그때 어떻게 분류했는지 기억해 보세요.

가장 왼쪽의 카드가 3, 두 번째 카드가 5, 세 번째 카드가 또 3이니까 빨리 첫 번째 카드 뒤에 넣어주세요. 두 번째 카드 이후에 넣으세요. 다섯 번째 카드가 또 3이라니, 하하, 대포가 탄생하네요.

어때요? 알고리즘은 삶의 곳곳에 이미 존재하며 우리의 삶과 혈액에 통합되어 있습니다.

다음은 위 사진에 대한 설명입니다.

이 사진을 보시면 삽입순으로 이해가 되실지 모르겠습니다. ,

배열 "순서 있는 배열 블록"과 "순서 없는 배열 블록"의 두 가지 유형으로 나뉩니다. 예, 첫 번째 패스에서는 "순서 없는 배열 블록"에서 숫자 20이 순서대로 추출됩니다. 배열 블록.

두 번째 패스에서는 "정렬되지 않은 배열 블록"에서 숫자 60이 추출되어 "정렬된 배열 블록", 즉 20, 60에 순서대로 배치됩니다.

세 번째 패스도 마찬가지지만, 10이 정렬된 배열의 값보다 작은 것으로 확인되어 20과 60의 위치를 ​​다시 이동하여 10의 위치를 ​​확보한다는 차이점이 있습니다. 삽입됩니다.

그러면 이 규칙에 따라 모든 삽입이 완료될 수 있습니다.

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

namespace InsertSort
{
 public class Program
 {
  static void Main(string[] args)
  {
   List<int> list = new List<int>() { 3, 1, 2, 9, 7, 8, 6 };

   Console.WriteLine("排序前：" + string.Join(",", list));

   InsertSort(list);

   Console.WriteLine("排序后：" + string.Join(",", list));
  }

  static void InsertSort(List<int> list)
  {
   //无须序列
   for (int i = 1; i < list.Count; i++)
   {
    var temp = list[i];

    int j;

    //有序序列
    for (j = i - 1; j >= 0 && temp < list[j]; j--)
    {
     list[j + 1] = list[j];
    }
    list[j + 1] = temp;
   }
  }
 }
}

Hill 정렬:

"삽입 정렬"을 보세요: 실제로는 그렇지 않습니다. 't 단점을 찾기가 어렵습니다.

데이터가 "

5, 4, 3, 2, 1"인 경우 이때 레코드를 삽입합니다. "정렬되지 않은 블록" "정렬된 블록"에 도달하면 붕괴가 예상되며 삽입할 때마다 위치가 이동됩니다. 이때 삽입 정렬의 효율성을 상상할 수 있습니다.

쉘은 이러한 약점을 기반으로 알고리즘을 개선하고 "

축소 증분 정렬 방법"이라는 아이디어를 통합했습니다. 실제로는 매우 간단하지만 주목해야 할 점은 다음과 같습니다.

증분은 무작위가 아니라 패턴을 따릅니다.

우선 증분을 구하는 방법을 명확히 해야 합니다.

첫 번째 증분을 구하는 방법은 d=count/입니다. 2;

두 번째 증분을 취하는 방법은 다음과 같습니다: d=(count/2)/2;

마지막으로, 때까지: d=1;

보세요. 위 그림에서 관찰되는 현상:

d=3일 때: 40과 50을 비교합니다. 50이 더 크기 때문에 교환이 없습니다.

20과 30을 비교하면 30이 크기 때문에 교환이 없습니다.

80과 60을 비교해보세요. 60이 더 작으니 교환하세요.

d=2인 경우: 40과 60을 비교하고 교환하지 않고, 60과 30을 교환합니다. 이때 교환된 30은 이전 40보다 작아서 40과 30을 교환해야 하므로 위 그림에 나와 있습니다.

교환하지 않고 20과 50을 비교하고, 교환하지 않고 50과 80을 계속 비교합니다.

d=1인 경우: 앞서 말한 삽입 정렬인데 이때 순서가 거의 순서대로 정렬되어 있어 삽입 정렬의 성능이 크게 향상됩니다.

'힐 정렬'은 '삽입 정렬'을 개선한 것이므로 10,000개의 숫자 중에서 얼마나 빨라질 수 있는지 비교해 볼까요?

테스트해보겠습니다:

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

namespace ShellSort
{
 public class Program
 {
  static void Main(string[] args)
  {
   //5次比较
   for (int i = 1; i <= 5; i++)
   {
    List<int> list = new List<int>();

    //插入1w个随机数到数组中
    for (int j = 0; j < 10000; j++)
    {
     Thread.Sleep(1);
     list.Add(new Random((int)DateTime.Now.Ticks).Next(10000, 1000000));
    }

    List<int> list2 = new List<int>();
    list2.AddRange(list);

    Console.WriteLine("\n第" + i + "次比较：");

    Stopwatch watch = new Stopwatch();

    watch.Start();
    InsertSort(list);
    watch.Stop();

    Console.WriteLine("\n插入排序耗费的时间：" + watch.ElapsedMilliseconds);
    Console.WriteLine("输出前十个数:" + string.Join(",", list.Take(10).ToList()));

    watch.Restart();
    ShellSort(list2);
    watch.Stop();

    Console.WriteLine("\n希尔排序耗费的时间：" + watch.ElapsedMilliseconds);
    Console.WriteLine("输出前十个数:" + string.Join(",", list2.Take(10).ToList()));

   }
  }

  ///<summary>
/// 希尔排序
///</summary>
///<param name="list"></param>
  static void ShellSort(List<int> list)
  {
   //取增量
   int step = list.Count / 2;

   while (step >= 1)
   {
    //无须序列
    for (int i = step; i < list.Count; i++)
    {
     var temp = list[i];

     int j;

     //有序序列
     for (j = i - step; j >= 0 && temp < list[j]; j = j - step)
     {
      list[j + step] = list[j];
     }
     list[j + step] = temp;
    }
    step = step / 2;
   }
  }

  ///<summary>
/// 插入排序
///</summary>
///<param name="list"></param>
  static void InsertSort(List<int> list)
  {
   //无须序列
   for (int i = 1; i < list.Count; i++)
   {
    var temp = list[i];

    int j;

    //有序序列
    for (j = i - 1; j >= 0 && temp < list[j]; j--)
    {
     list[j + 1] = list[j];
    }
    list[j + 1] = temp;
   }
  }
 }
}

스크린샷은 다음과 같습니다:

희망합니다 보시다시피 정렬이 많이 최적화되었습니다. w-레벨 정렬에서는 그 차이가 70배 이상입니다.

병합 정렬:

개인적으로 우리가 쉽게 이해할 수 있는 정렬은 기본적으로 O(n^2)이고, 더 이해하기 어려운 정렬은 기본적으로 O(n^2) N(LogN)이므로 병합 정렬도 상대적으로 이해하기 어렵습니다. 특히

코드를 작성하는 데는 오후 내내 걸렸습니다. 헤헤.

먼저 그림을 보세요:

병합 정렬에는 두 가지 작업이 있습니다.

第一： “分”, 就是将数组尽可能的分，一直分到原子级别。

第二： “并”，将原子级别的数两两合并排序，最后产生结果。

代码：

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

namespace MergeSort
{
 class Program
 {
  static void Main(string[] args)
  {
   int[] array = { 3, 2, 1, 8, 9, 0 };

   MergeSort(array, new int[array.Length], 0, array.Length - 1);

   Console.WriteLine(string.Join(",", array));
  }

  ///<summary>
/// 数组的划分
///</summary>
///<param name="array">待排序数组</param>
///<param name="temparray">临时存放数组</param>
///<param name="left">序列段的开始位置，</param>
///<param name="right">序列段的结束位置</param>
  static void MergeSort(int[] array, int[] temparray, int left, int right)
  {
   if (left < right)
   {
    //取分割位置
    int middle = (left + right) / 2;

    //递归划分数组左序列
    MergeSort(array, temparray, left, middle);

    //递归划分数组右序列
    MergeSort(array, temparray, middle + 1, right);

    //数组合并操作
    Merge(array, temparray, left, middle + 1, right);
   }
  }

  ///<summary>
/// 数组的两两合并操作
///</summary>
///<param name="array">待排序数组</param>
///<param name="temparray">临时数组</param>
///<param name="left">第一个区间段开始位置</param>
///<param name="middle">第二个区间的开始位置</param>
///<param name="right">第二个区间段结束位置</param>
  static void Merge(int[] array, int[] temparray, int left, int middle, int right)
  {
   //左指针尾
   int leftEnd = middle - 1;

   //右指针头
   int rightStart = middle;

   //临时数组的下标
   int tempIndex = left;

   //数组合并后的length长度
   int tempLength = right - left + 1;

   //先循环两个区间段都没有结束的情况
   while ((left <= leftEnd) && (rightStart <= right))
   {
    //如果发现有序列大，则将此数放入临时数组
    if (array[left] < array[rightStart])
     temparray[tempIndex++] = array[left++];
    else
     temparray[tempIndex++] = array[rightStart++];
   }

   //判断左序列是否结束
   while (left <= leftEnd)
    temparray[tempIndex++] = array[left++];

   //判断右序列是否结束
   while (rightStart <= right)
    temparray[tempIndex++] = array[rightStart++];

   //交换数据
   for (int i = 0; i < tempLength; i++)
   {
    array[right] = temparray[right];
    right--;
   }
  }
 }
}

结果图：

ps:

插入排序的时间复杂度为：O(N^2)

希尔排序的时间复杂度为：平均为：O(N^3/2)

最坏：O(N^2)

归并排序时间复杂度为： O(NlogN)

空间复杂度为: O(N)

위 내용은 C# 클래식 정렬 알고리즘의 그래픽 코드에 대한 자세한 설명(2부)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!