冒泡排序
简单 运行慢
1.比较两个数据
2.左边大交换两个数据
3.向右移重复1.2
/// <summary>
/// 冒泡排序
/// </summary>
/// <param name="arr"></param>
public static void BubbleSort(List<int>arr)
{
//控制冒泡次数
for (int i = 0; i < arr.Count-1; i++)
{
//i,i+1
for (int j = 0; j < arr.Count-1-i; j++)
{
//两两比较 i i+1
if (arr[j]>arr[j+1])
{
Swap(arr, j, j + 1);
}
}
}
}
/// <summary>
/// 两两交换
/// </summary>
/// <param name="arr"></param>
/// <param name="j"></param>
/// <param name="v"></param>
private static void Swap(List<int> arr, int j, int v)
{
int temp = arr[j];
arr[j] = arr[v];
arr[v] = temp;
}
选择排序
选出最小才交换 在冒泡基础上改良 交换最少
1.扫描整个序列
2.从中挑选出最小的数据项
3.将最小的数据项放置到合适的位置
/// <summary>
/// 选择排序
/// </summary>
/// <param name="arr"></param>
public static void SelectSort(List<int>arr)
{
for (int i = 0; i < arr.Count-1; i++)
{
//为i位置找到最小值
//假设当前位置恰好最小
int min = i;
//验证是否最小
for (int j = i+1; j < arr.Count; j++)
{
//是否发现更小的位置
if (arr[min]>arr[j])
{
min = j;
}
}
//最小位置是否真的最小
if (min!=i)
{
//假设失败交换
Swap(arr,min,i);
}
}
}
/// <summary>
/// 两两交换
/// </summary>
/// <param name="arr"></param>
/// <param name="j"></param>
/// <param name="v"></param>
private static void Swap(List<int> arr, int j, int v)
{
int temp = arr[j];
arr[j] = arr[v];
arr[v] = temp;
}
插入排序
是简单排序里最好的一种 稍微麻烦
1.假设部分有序（一般设第一个数据项为第一部分）
2.其他输入依次插入之前的有序序列
若序列基本有序 此排序最优
要注意为待插入元素找到合适位置
序列逆序才和冒泡效率一样
/// <summary>
/// 插入排序 赋值法
/// </summary>
/// <param name="arr"></param>
public static void InsertSort(List<int> arr)
{
for (int i = 1; i < arr.Count; i++)
{
//为arr[i]找到插入位置
//同时设置监视哨
int temp = arr[i];
int index = i;
while (index > 0 && arr[index - 1] > temp)
{
//移动数据
arr[index] = arr[index - 1];
index--;//不能减到0
}
//将数据插入序列中
arr[index] = temp;
}
}
/// <summary>
/// 不带监视哨的插入排序 交换法
/// </summary>
/// <param name="arr"></param>
public static void InsertSort2(List<int> arr)
{
for (int i = 1; i < arr.Count; i++)
{
for (int j = i; j >0; j--)
{
if (arr[j-1]>arr[j])
{
Swap(arr, j - 1, j);
}
else
{
break;
}
}
}
}
/// <summary>
/// 两两交换
/// </summary>
/// <param name="arr"></param>
/// <param name="j"></param>
/// <param name="v"></param>
private static void Swap(List<int> arr, int j, int v)
{
int temp = arr[j];
arr[j] = arr[v];
arr[v] = temp;
}
希尔排序
基于无监视哨插入排序一种改进
逐渐趋近于有序
这个数和这个数之后第3个数 组成一组排序
/// <summary>
/// 希尔排序
/// </summary>
/// <param name="arr"></param>
public static void ShellSort(List<int> arr)
{
for (int g = arr.Count / 2; g >= 1; g /= 2)
{
for (int i = g; i < arr.Count; i++)
{
for (int j = i - g; j >= 0; j-=g)
{
if (arr[j] > arr[j + g])
{
Swap(arr, j + g, j);
}
else
{
break;
}
}
}
}
}
/// <summary>
/// 两两交换
/// </summary>
/// <param name="arr"></param>
/// <param name="j"></param>
/// <param name="v"></param>
private static void Swap(List<int> arr, int j, int v)
{
int temp = arr[j];
arr[j] = arr[v];
arr[v] = temp;
}
快速排序
最常用的一种排序 速度快
1.把序列划分为两个部分：左边较小的部分 右边较大的部分
2.调用自己为左边排序
3.调用自己为右边排序
/// <summary>
/// 为序列的某个部分进行划分 左小右大
/// </summary>
/// <param name="arr">序列</param>
/// <param name="start">开始位置</param>
/// <param name="end">结束位置</param>
public static void QuickSort(List<int> arr, int start, int end)
{
if (start < end)
{
int s = start;
int e = end;
//临界值位置的标量
bool isStart = true;
while (s < e)
{
if (arr[s] > arr[e])
{
Swap(arr, s, e);
//标量转换
isStart = !isStart;
}
//移动索引位置
if (isStart)
{
e--;
}
else
{
s++;
}
}
//将序列划分成了：
//左边:start→（e-1）
QuickSort(arr,start, e - 1);
//右边：s+1→end
QuickSort(arr, s + 1, end);
}
}
/// <summary>
/// 两两交换
/// </summary>
/// <param name="arr"></param>
/// <param name="j"></param>
/// <param name="v"></param>
private static void Swap(List<int> arr, int j, int v)
{
int temp = arr[j];
arr[j] = arr[v];
arr[v] = temp;
}
所用时间对比
void Start()
{
List<int> arr = CreateArr(10000);
Stopwatch time = new Stopwatch();//要using System.Diagnostics;
time.Start();
//BubbleSort(arr); 3020
//SelectSort(arr); 1345
//InsertSort(arr); 988
//InsertSort2(arr);2123
//ShellSort(arr);23
//QuickSort(arr,0,arr.Count-1);7
time.Stop();
UnityEngine.Debug.Log(time.ElapsedMilliseconds);
}
/// <summary>
/// 创建一个很大的List
/// </summary>
/// <param name="v"></param>
/// <returns></returns>
public static List<int> CreateArr(int v)
{
List<int> arr = new List<int>();
System.Random r = new System.Random();
for (int i = 0; i < v; i++)
{
arr.Add(r.Next(0, v));
}
return arr;
}
后面的数字就是时间对比 可见快排最快
