using System;
namespace SortAlgorithm
{
internal class Program
{
static void BubbleSort(int[] arr)//常规冒泡排序
{
for (int i = 0; i < arr.Length - 1; i++)
{
for (int j = 0; j < arr.Length - 1 - i; j++)
{
if (arr[j] > arr[j + 1])//将最大的数往后移
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
static void OptimizeBubbleSort(int[] arr)//优化的冒泡排序，减少循环的次数
{
for(int i=0;i<arr.Length-1;i++)
{
bool isEnter = false;
for(int j=0;j<arr.Length-1-i;j++)
{
if(arr[j] > arr[j+1])
{
int temp=arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isEnter=true;
}
}
if(!isEnter)//没有出现交换说明已经排好序了，可以直接跳出
{
break;
}
}
}
//使用冒泡排序对学生分数进行排名
static void ScoreSort<T>(T[] student,Func<T,T,bool> compareScore)
{
for (int i = 0; i < student.Length - 1; i++)
{
bool isEnter = false;
for (int j = 0; j < student.Length - 1 - i; j++)
{
if (compareScore(student[j], student[j+1]))
{
T temp = student[j];
student[j] = student[j + 1];
student[j + 1] = temp;
isEnter = true;
}
}
if (!isEnter)//没有出现交换说明已经排好序了，可以直接跳出
{
break;
}
}
}
static void Main(string[] args)
{
int[] arr = { 2, 4, 1, 3, 9, 3, 5 };
//BubbleSort(arr);
OptimizeBubbleSort(arr);
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
Student[] stu = { new Student("张三", 100), new Student("李四", 24), new Student("王五", 78), new Student("赵六", 78), new Student("钱七", 97) };
ScoreSort<Student>(stu, Student.CompareScore);
foreach(var item in stu)
{
Console.WriteLine(item);
}
}
}
public class Student
{
string name;
int score;
public string Name { get => name;set=> name = value; }
public int Score { get => score; set => score = value; }
public Student(string name,int score)
{
this.Name = name;
this.Score=score;
}
public override string ToString()//重写ToString
{
return Name+":"+Score;
}
public static bool CompareScore(Student s1,Student s2)
{
if (s1.Score > s2.Score) return true;
else return false;
}
}
}选择排序
using System;
namespace SortAlgorithm
{
internal class Program
{
static void SelectionSort(int[] arr)
{
for(int i=0;i<arr.Length-1;i++)
{
int minIndex = i;
for(int j=i+1;j<arr.Length;j++)
{
if(arr[j]<arr[minIndex])//找到并记录最小值的索引
{
minIndex = j;
}
}
if(minIndex!=i)//判断索引是否改变，改变则交换元素
{
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
static void Main(string[] args)
{
int[] arr = { 2, 4, 1, 3, 9, 3, 5 };
SelectionSort(arr);
for(int i=0;i<arr.Length;i++)
{
Console.WriteLine(arr[i]);
}
}
}
}插入排序
using System;
namespace SortAlgorithm
{
internal class Program
{
static void InsertionSort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int tempData = arr[i];
for(int j=i-1; j >= -1; j--)
{
if (j>=0&&tempData < arr[j])
arr[j+1] = arr[j];//数据后移
else
{
arr[j+1] = tempData;//初值替换
break;
}
}
}
}
static void Main(string[] args)
{
int[] arr = { 2, 4, 1, 3, 9, 3, 5 };
InsertionSort(arr);
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
}
}
}希尔排序
using System;
namespace SortAlgorithm
{
internal class Program
{
static void ShellSort(int[] arr)
{
int gap=arr.Length/2;
while(gap>0)
{
for(int i=gap;i<arr.Length;i++)//递进间隔为gap的数值索引
{
int temp = arr[i];
int j = i;
while (j >= gap && arr[j-gap]>temp)//使间隔为gap的元素交换排序
{
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap /= 2;//缩小元素的间隔gap
}
}
static void Main(string[] args)
{
int[] arr = { 2, 4, 1, 3, 9, 3, 5 };
ShellSort(arr);
for(int i=0;i<arr.Length;i++)
{
Console.WriteLine(arr[i]);
}
}
}
}归并排序
using System;
namespace SortAlgorithm
{
internal class Program
{
static void Merge(int[] arr, int left, int mid, int right)
{
int[] temp = new int[arr.Length];
int i, left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while ((left <= left_end) && (mid <= right))
{
if (arr[left] <= arr[mid])
{
temp[tmp_pos++] = arr[left++];
}
else
{
temp[tmp_pos++] = arr[mid++];
}
}
while (left <= left_end)
{
temp[tmp_pos++] = arr[left++];
}
while (mid <= right)
{
temp[tmp_pos++] = arr[mid++];
}
for (i = 0; i < num_elements; i++)
{
arr[right] = temp[right];
right--;
}
}
static void MergeSort(int[] arr, int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, (mid + 1), right);
Merge(arr, left, (mid + 1), right);
}
}
static void Main(string[] args)
{
int[] arr = { 2, 4, 1, 3, 9, 3, 5 };
MergeSort(arr,0,arr.Length-1);
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
}
}
}快速排序
using System;
namespace SortAlgorithm
{
internal class Program
{
public static void QuickSort(int[] arr, int left, int right)
{
if (left < right)
{
// 分治操作，将数组分为left~pivot和pivot+1~right两部分
int pivot = Partition(arr, left, right);
// 对左半边递归快排
QuickSort(arr, left, pivot - 1);
// 对右半边递归快排
QuickSort(arr, pivot + 1, right);
}
}
private static int Partition(int[] arr, int left, int right)
{
// 取第一个元素作为pivot
int pivot = arr[left];
while (left < right)
{
// 找到右半边第一个小于等于pivot的位置
while (left < right && arr[right] > pivot)
{
right--;
}
// 将该位置元素放入左半边
arr[left] = arr[right];
// 找到左半边第一个大于pivot的位置
while (left < right && arr[left] <= pivot)
{
left++;
}
// 将该位置元素放入右半边
arr[right] = arr[left];
}
// 将pivot插入到正确的位置
arr[left] = pivot;
return left;
}
static void Main(string[] args)
{
int[] arr = { 2, 4, 1, 3, 9, 3, 5 };
QuickSort(arr,0,arr.Length-1);
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
}
}
}堆排序
using System;
namespace SortAlgorithm
{
internal class Program
{
static void HeapSort(int[] arr)
{
int n = arr.Length;
for (int i = n / 2 - 1; i >= 0; i--)
{
Heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
Heapify(arr, i, 0);
}
}
static void Heapify(int[] arr, int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
{
largest = left;
}
if (right < n && arr[right] > arr[largest])
{
largest = right;
}
if (largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
Heapify(arr, n, largest);
}
}
static void Main(string[] args)
{
int[] arr = { 2, 4, 1, 3, 9, 3, 5 };
HeapSort(arr);
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
}
}
}计数排序
using System;
namespace SortAlgorithm
{
internal class Program
{
public static void CountingSort(int[] arr)
{
int len = arr.Length;
if (len <= 1)
{
return;
}
// 找到数组中最大值和最小值
int max = arr[0], min = arr[0];
for (int i = 1; i < len; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
// 创建计数数组
int[] count = new int[max - min + 1];
// 计数
for (int i = 0; i < len; i++)
{
count[arr[i] - min]++;
}
// 累加计数
for (int i = 1; i < count.Length; i++)
{
count[i] += count[i - 1];
}
// 排序
int[] sortedArr = new int[len];
for (int i = len - 1; i >= 0; i--)
{
sortedArr[--count[arr[i] - min]] = arr[i];
}
// 复制回原数组
for (int i = 0; i < len; i++)
{
arr[i] = sortedArr[i];
}
}
static void Main(string[] args)
{
int[] arr = { 2, 4, 1, 3, 9, 3, 5 };
CountingSort(arr);
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
}
}
}桶排序
using System;
namespace SortAlgorithm
{
internal class Program
{
static void BucketSort(int[] data)
{
// 确定要排序的数的范围（假设0 <= data[i] <= 99）
const int MAX_VALUE = 99;
// 初始化桶数组
int[] bucket = new int[MAX_VALUE + 1];
for (int i = 0; i < bucket.Length; ++i)
{
bucket[i] = 0;
}
// 统计每个数出现次数
for (int i = 0; i < data.Length; ++i)
{
++bucket[data[i]];
}
// 将桶中的数据按顺序合并到结果数组中
int pos = 0;
for (int i = 0; i < bucket.Length; ++i)
{
for (int j = 0; j < bucket[i]; ++j)
{
data[pos++] = i;
}
}
}
static void Main(string[] args)
{
int[] arr = { 2, 4, 1, 3, 9, 3, 5 };
BucketSort(arr);
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
}
}
}基数排序
using System;
namespace SortAlgorithm
{
internal class Program
{
static void RadixSort(int[] arr)
{
int len = arr.Length;
if (len <= 1)
{
return;
}
// 找到数组中最大值
int max = arr[0];
for (int i = 1; i < len; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
// 计算最大值的位数
int digit = 1;
while (max / digit > 0)
{
CountingSortByDigit(arr, digit);
digit *= 10;
}
}
static void CountingSortByDigit(int[] arr, int digit)
{
int len = arr.Length;
int[] count = new int[10];
// 统计每个数字出现的次数
for (int i = 0; i < len; i++)
{
int num = (arr[i] / digit) % 10;
count[num]++;
}
// 累加次数
for (int i = 1; i < count.Length; i++)
{
count[i] += count[i - 1];
}
// 排序
int[] sortedArr = new int[len];
for (int i = len - 1; i >= 0; i--)
{
int num = (arr[i] / digit) % 10;
sortedArr[--count[num]] = arr[i];
}
// 复制回原数组
for (int i = 0; i < len; i++)
{
arr[i] = sortedArr[i];
}
}
static void Main(string[] args)
{
int[] arr = { 2, 4, 1, 3, 9, 3, 5 };
RadixSort(arr);
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
}
}
}因篇幅问题不能全部显示，请点此查看更多更全内容