이 글에서는 C#의 7가지 고전 정렬 알고리즘인 직접 삽입 정렬, 힐 정렬, 병합 정렬 시리즈의 다음 부분을 주로 소개합니다. 🎜>
오늘은 마지막 세 가지 정렬인 직접 삽입 정렬, 힐 정렬, 병합 정렬에 대해 말씀드리겠습니다.직접 삽입 정렬:
이러한 정렬은 실제로 매우 이해하기 쉽습니다. 매우 현실적인 예는 우리가 무작위로 카드를 잡을 때입니다. 포커 카드를 크기별로 분류해야 하는데 30초가 지나면 포커 카드가 3, 5, 4개로 분류됩니다. 와... 그때 어떻게 분류했는지 기억해 보세요. 가장 왼쪽의 카드가 3, 두 번째 카드가 5, 세 번째 카드가 또 3이니까 빨리 첫 번째 카드 뒤에 넣어주세요. 두 번째 카드 이후에 넣으세요. 다섯 번째 카드가 또 3이라니, 하하, 대포가 탄생하네요. 어때요? 알고리즘은 삶의 곳곳에 이미 존재하며 우리의 삶과 혈액에 통합되어 있습니다. 다음은 위 사진에 대한 설명입니다.
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"인 경우 이때 레코드를 삽입합니다. "정렬되지 않은 블록" "정렬된 블록"에 도달하면 붕괴가 예상되며 삽입할 때마다 위치가 이동됩니다. 이때 삽입 정렬의 효율성을 상상할 수 있습니다.
쉘은 이러한 약점을 기반으로 알고리즘을 개선하고 "축소 증분 정렬 방법"이라는 아이디어를 통합했습니다. 실제로는 매우 간단하지만 주목해야 할 점은 다음과 같습니다.
증분은 무작위가 아니라 패턴을 따릅니다.
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;
}
}
}
}
병합 정렬:
개인적으로 우리가 쉽게 이해할 수 있는 정렬은 기본적으로 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
