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

이 글은 주로 C#, 버블 정렬, 퀵 정렬 등 7가지 고전 정렬 알고리즘 시리즈의 첫 번째 부분을 소개합니다. 관심 있는 친구들이 참고할 수 있습니다.

오늘은 기사 시작 부분에서 알고리즘은 프로그램 개발에 있어서 칼과 같습니다.

실제 정렬 문제의 경우 알고리즘에는 성공하는 데 도움이 되는 일곱 개의 날카로운 칼이 있습니다.

우선 정렬에는 4가지 종류가 있습니다.

교환 정렬: 버블 정렬과 퀵 정렬이 있습니다.

선택 정렬: 직접 선택 정렬과 힙 정렬이 포함됩니다.

삽입 정렬: 직접 삽입 정렬과 Hill 정렬이 포함됩니다.

병합 정렬: 병합 정렬.

버블 정렬:

먼저 "버블 정렬"을 직접 디자인해 보겠습니다. 이 정렬의 매우 현실적인 예는 다음과 같습니다. 모래를 한 줌 쥐고 물에 넣으면 모래는 즉시 물 밑으로 가라앉습니다. 모래 위의 먼지는 관성에 의해 일시적으로 물 밑으로 가라앉지만, 즉시 거품처럼 떠오를 것입니다. , 그리고 마침내 진실이 밝혀질 것입니다.

거품이 나는 생각에 대해서는 공식적인 이론을 언급하지 않을 것이며, 그런 말을 게시하지 않을 것입니다.

그럼 위 사진을 찍어보겠습니다.

버블링 효과를 얻으려면 일련의 숫자를 세워서 보아야 합니다. 어떻게 거품? 무거운 것은 바닥으로 가라앉고 가벼운 것은 뜨는 것을 어떻게 이해합니까?

1단계: 40과 20을 비교한 결과 40이 최고이고 교환할 필요가 없음을 확인합니다.

두 번째 단계: 그런 다음 한 단계 더 나아가십시오. 즉, 20과 30을 비교하십시오. 30이 상사라고 판단되면 교환해야 합니다.

3단계: 교환된 20을 10과 비교하여 자신이 주인이고 교환할 필요가 없음을 확인합니다.

4단계: 10을 50으로 교환합니다. 50이 우두머리라는 것을 알았으므로 교환합니다.

드디어 순회 후 배열에서 가장 작은 숫자를 보냈습니다. 보세요. 목표를 향해 한 걸음 더 나아갔습니다.

이제 모두가 무슨 생각을 하는지 알 것 같으니, 퀵큐로 승부를 펼칠 것을 강력히 요구하겠습니다.

아아아아아

우우, 정리된 신체검사 보고서 두 장을 보니 마음이 식어버렸고, 버블은 퀵랭킹으로 KO당했고, 참으로 비참합니다. 사람들이 버블링 효율이 낮다고 하는 것은 당연하지만 실제로는 매우 낮습니다.

퀵 정렬:

KO 버블링이 가능하기 때문에 즉시 관심이 생겼습니다. 퀵 정렬이 너무 빠르기 때문에 주의 깊게 연구해야 합니다. 우선 위 그림은

그림에서 볼 수 있는 내용은 다음과 같습니다.

왼쪽 포인터, 오른쪽 포인터, 기본 참조 숫자.

사실 아이디어는 매우 간단합니다. 즉, 첫 번째 순회 단계를 통해 배열의 절단 지점을 찾는 것입니다(왼쪽 및 오른쪽 포인터가 일치하도록 만들기).

1단계: 먼저 배열의 왼쪽 위치에서 숫자(20)를 기본 참조 개체로 사용합니다.

2단계: (base)보다 작은 숫자를 찾을 때까지 배열의 오른쪽 위치에서 앞으로 검색합니다.

찾은 경우 이 숫자를 왼쪽 위치에 할당합니다(즉, 10 20),

에 할당됨 이때 배열은 10, 40, 50, 10, 60,

왼쪽 및 오른쪽 포인터는 각각 앞과 뒤가 10입니다.

3단계: (base)보다 큰 숫자를 찾을 때까지 배열의 왼쪽 위치에서 뒤로 검색합니다.

찾은 경우 이 숫자를 오른쪽 위치(즉, 40)에 할당합니다. 10),

이때 배열은 10, 40, 50, 40, 60,

왼쪽 포인터와 오른쪽 포인터는 각각 40 전후입니다.

4단계: 왼쪽과 오른쪽 포인터가 일치할 때까지 "두 번째, 세 번째" 단계를 반복합니다.

마지막으로 (베이스)를 40자리에 삽입하고,

이때 배열은 값은 10, 20, 50, 40, 60입니다. 이 시점에서 정렬이 완료됩니다.

5단계: 이때 20이 배열 내부로 몰래 들어갔습니다. 20의 왼쪽에 있는 숫자 그룹은 20보다 작고, 오른쪽에 있는 숫자 그룹은 입니다. 20보다 큽니다.

            以20为切入点对左右两边数按照"第一，第二，第三，第四"步骤进行，最终快排大功告成。 

同样，我们把自己设计的快排跟类库提供的快拍比较一下。

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

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

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

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

        Stopwatch watch = new Stopwatch();

        watch.Start();
        var result = list.OrderBy(single => single).ToList();
        watch.Stop();

        Console.WriteLine("\n系统定义的快速排序耗费时间：" + watch.ElapsedMilliseconds);
        Console.WriteLine("输出前是十个数:" + string.Join(",", result.Take(10).ToList()));

        watch.Start();
        new QuickSortClass().QuickSort(list, 0, list.Count - 1);
        watch.Stop();

        Console.WriteLine("\n俺自己写的快速排序耗费时间：" + watch.ElapsedMilliseconds);
        Console.WriteLine("输出前是十个数:" + string.Join(",", list.Take(10).ToList()));

      }
    }
  }

  public class QuickSortClass
  {

    ///<summary>
/// 分割函数
///</summary>
///<param name="list">待排序的数组</param>
///<param name="left">数组的左下标</param>
///<param name="right"></param>
///<returns></returns>
    public int pision(List<int> list, int left, int right)
    {
      //首先挑选一个基准元素
      int baseNum = list[left];

      while (left < right)
      {
        //从数组的右端开始向前找，一直找到比base小的数字为止(包括base同等数)
        while (left < right && list[right] >= baseNum)
          right = right - 1;

        //最终找到了比baseNum小的元素，要做的事情就是此元素放到base的位置
        list[left] = list[right];

        //从数组的左端开始向后找，一直找到比base大的数字为止（包括base同等数）
        while (left < right && list[left] <= baseNum)
          left = left + 1;


        //最终找到了比baseNum大的元素，要做的事情就是将此元素放到最后的位置
        list[right] = list[left];
      }
      //最后就是把baseNum放到该left的位置
      list[left] = baseNum;

      //最终，我们发现left位置的左侧数值部分比left小，left位置右侧数值比left大
//至此，我们完成了第一篇排序
      return left;
    }

    public void QuickSort(List<int> list, int left, int right)
    {
      //左下标一定小于右下标，否则就超越了
      if (left < right)
      {
        //对数组进行分割，取出下次分割的基准标号
        int i = pision(list, left, right);

        //对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        QuickSort(list, left, i - 1);

        //对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        QuickSort(list, i + 1, right);
      }
    }
  }
}

不错，快排就是快，难怪内库非要用他来作为排序的标准。 

嗯，最后要分享下：

冒泡的时间复杂度为：0(n) - 0(n^2)

快排的时间复杂度为：

    平均复杂度：N(logN)

    最坏复杂度： 0(n^2)

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