이 글은 주로 C#, 버블 정렬, 퀵 정렬 등 7가지 고전 정렬 알고리즘 시리즈의 첫 번째 부분을 소개합니다. 관심 있는 친구들이 참고할 수 있습니다.
오늘은 기사 시작 부분에서 알고리즘은 프로그램 개발에 있어서 칼과 같습니다.
실제 정렬 문제의 경우 알고리즘에는 성공하는 데 도움이 되는 일곱 개의 날카로운 칼이 있습니다.
우선 정렬에는 4가지 종류가 있습니다.
교환 정렬: 버블 정렬과 퀵 정렬이 있습니다.
선택 정렬: 직접 선택 정렬과 힙 정렬이 포함됩니다.
삽입 정렬: 직접 삽입 정렬과 Hill 정렬이 포함됩니다.
병합 정렬: 병합 정렬.
버블 정렬:먼저 "버블 정렬"을 직접 디자인해 보겠습니다. 이 정렬의 매우 현실적인 예는 다음과 같습니다. 모래를 한 줌 쥐고 물에 넣으면 모래는 즉시 물 밑으로 가라앉습니다. 모래 위의 먼지는 관성에 의해 일시적으로 물 밑으로 가라앉지만, 즉시 거품처럼 떠오를 것입니다. , 그리고 마침내 진실이 밝혀질 것입니다.
거품이 나는 생각에 대해서는 공식적인 이론을 언급하지 않을 것이며, 그런 말을 게시하지 않을 것입니다.
그럼 위 사진을 찍어보겠습니다.
버블링 효과를 얻으려면 일련의 숫자를 세워서 보아야 합니다. 어떻게 거품? 무거운 것은 바닥으로 가라앉고 가벼운 것은 뜨는 것을 어떻게 이해합니까?1단계: 40과 20을 비교한 결과 40이 최고이고 교환할 필요가 없음을 확인합니다.
두 번째 단계: 그런 다음 한 단계 더 나아가십시오. 즉, 20과 30을 비교하십시오. 30이 상사라고 판단되면 교환해야 합니다.
3단계: 교환된 20을 10과 비교하여 자신이 주인이고 교환할 필요가 없음을 확인합니다.
4단계: 10을 50으로 교환합니다. 50이 우두머리라는 것을 알았으므로 교환합니다.
드디어 순회 후 배열에서 가장 작은 숫자를 보냈습니다. 보세요. 목표를 향해 한 걸음 더 나아갔습니다.
이제 모두가 무슨 생각을 하는지 알 것 같으니, 퀵큐로 승부를 펼칠 것을 강력히 요구하겠습니다.
아아아아아
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!