[ContextMenu("output")]
public void OutPut()
{
int[] arrays = new int[] { 550, 1206, 840, 620, 10, 210 };
//1.冒泡排序
//Bubble(arrays);
//2.简单选择排序
//SimpleSort(arrays);
//3.插入排序
//InsertSort(arrays);
//4.希尔排序
//Shell(arrays);
//5.合并排序
//MergeSort(arrays);
//6.快速排序
//QuickSort(arrays);
//7.堆积排序
HeapSortFunction(arrays);
//8.基数排序
//Radix(arrays);
string log = string.Empty;
foreach (var item in arrays)
{
log += item + " ";
}
Debug.Log(log);
}
private void Bubble(int[] arrays)
{
int length = arrays.Length;
int temp = 0;
bool isSwitch = false;
for (int j = 0; j < length; j++)
{
for (int i = 0; i < length - 1 - j; i++)
{
if (arrays[i + 1] < arrays[i])
{
temp = arrays[i];
arrays[i] = arrays[i + 1];
arrays[i + 1] = temp;
isSwitch = true;
}
}
if (!isSwitch) break;
else isSwitch = false;
}
}
private void SimpleSort(int[] arrays)
{
int length = arrays.Length;
int min = 0;
int temp;
for (int i = 0; i < length; i++)
{
min = i;
for (int j = i + 1; j < length; j++)
{
if (arrays[j] < arrays[min])
{
min = j;
}
}
if (i != min)
{
temp = arrays[min];
arrays[min] = arrays[i];
arrays[i] = temp;
}
}
}
private void InsertSort(int[] arrays)
{
int length = arrays.Length;
int temp;
int i, j;
for (i = 1; i < length; i++)
{
temp = arrays[i];
j = i - 1;
while (j >= 0 && temp < arrays[j])
{
arrays[j + 1] = arrays[j];
j--;
}
arrays[j + 1] = temp;
}
}
private void Shell(int[] arrays)
{
int length = arrays.Length;
int temp;
int i, j;
int jump;
jump = length / 2;
while (jump != 0)
{
for (i = jump; i < length; i++)
{
temp = arrays[i];
j = i - jump;
while (j >= 0 && temp < arrays[j])
{
arrays[j + jump] = arrays[j];
j = j - jump;
}
arrays[j + jump] = temp;
}
jump /= 2;
}
}
private void MergeSort(int[] arrays)
{
int length = arrays.Length;
int middle = length / 2;
if (length > 1)
{
int[] left = new int[middle];
int[] right = new int[length - middle];
for (int i = 0; i < middle; i++)
{
left[i] = arrays[i];
}
for (int i = middle; i < length; i++)
{
right[i - middle] = arrays[i];
}
MergeSort(left);
MergeSort(right);
merge(arrays, left, right);
}
}
//合并数组，升序
private void merge(int[] result, int[] left, int[] right)
{
int i = 0, l = 0, r = 0;
while (l < left.Length && r < right.Length)
{
if (left[l] < right[r])
{
result[i] = left[l];
i++;
l++;
}
else
{
result[i] = right[r];
i++;
r++;
}
}
while (r < right.Length)
{//如果右边剩下合并右边的
result[i] = right[r];
r++;
i++;
}
while (l < left.Length)
{
result[i] = left[l];
l++;
i++;
}
}
private void QuickSort(int[] arrays)
{
quick(arrays, arrays.Length, 0, arrays.Length - 1);
}
private void quick(int[] d, int size, int lf, int rg)
{
int tmp;
int lf_idx;
int rg_idx;
//左侧挑选的数小于右侧
if (lf < rg)
{
//lf为第一项，标志位
lf_idx = lf + 1;
rg_idx = rg;
while (true)
{
for (int i = lf + 1; i <= rg; i++) //从左向右找出第一个大于标志位的数
{
if (d[i] >= d[lf])
{
lf_idx = i;
break;
}
lf_idx++;
}
for (int j = rg; j >= lf + 1; j--) //从右向左找出第一个小于标志位的数
{
if (d[j] <= d[lf])
{
rg_idx = j;
break;
}
rg_idx--;
}
if (lf_idx < rg_idx)// 右侧第一个小于标志位的数 恰好在 左侧第一个大于标志位的数 的右侧，那这两个数直接对换位置
//然后继续检测下一组数，否则跳出循环
{
tmp = d[lf_idx];
d[lf_idx] = d[rg_idx];
d[rg_idx] = tmp;
}
else
{
break;
}
}
if (rg_idx <= lf_idx)
{
tmp = d[lf];
d[lf] = d[rg_idx];
d[rg_idx] = tmp;
quick(d, size, lf, rg_idx - 1);
quick(d, size, rg_idx + 1, rg);
}
}
}
//堆排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）
private static void HeapSortFunction(int[] array)
{
BuildMaxHeap(array); //创建大顶推（初始状态看做：整体无序）
for (int i = array.Length - 1; i > 0; i--)
{
Swap(ref array[0], ref array[i]); //将堆顶元素依次与无序区的最后一位交换（使堆顶元素进入有序区）
MaxHeapify(array, 0, i); //重新将无序区调整为大顶堆
}
}
///<summary>
/// 创建大顶推（根节点大于左右子节点）
///</summary>
///<param name="array">待排数组</param>
private static void BuildMaxHeap(int[] array)
{
//根据大顶堆的性质可知：数组的前半段的元素为根节点，其余元素都为叶节点
for (int i = array.Length / 2 - 1; i >= 0; i--) //从最底层的最后一个根节点开始进行大顶推的调整
{
MaxHeapify(array, i, array.Length); //调整大顶堆
}
}
///<summary>
/// 大顶推的调整过程
///</summary>
///<param name="array">待调整的数组</param>
///<param name="currentIndex">待调整元素在数组中的位置（即：根节点）</param>
///<param name="heapSize">堆中所有元素的个数</param>
private static void MaxHeapify(int[] array, int currentIndex, int heapSize)
{
int left = 2 * currentIndex + 1; //左子节点在数组中的位置
int right = 2 * currentIndex + 2; //右子节点在数组中的位置
int large = currentIndex; //记录此根节点、左子节点、右子节点 三者中最大值的位置
if (left < heapSize && array[left] > array[large]) //与左子节点进行比较
{
large = left;
}
if (right < heapSize && array[right] > array[large]) //与右子节点进行比较
{
large = right;
}
if (currentIndex != large) //如果 currentIndex != large 则表明 large 发生变化（即：左右子节点中有大于根节点的情况）
{
Swap(ref array[currentIndex], ref array[large]); //将左右节点中的大者与根节点进行交换（即：实现局部大顶堆）
MaxHeapify(array, large, heapSize); //以上次调整动作的large位置（为此次调整的根节点位置），进行递归调整
}
}
///<summary>
/// 交换函数
///</summary>
///<param name="a">元素a</param>
///<param name="b">元素b</param>
private static void Swap(ref int a, ref int b)
{
int temp = 0;
temp = a;
a = b;
b = temp;
}
private void Radix(int[] arrays)
{
int size = arrays.Length;
for (int n = 1; n <= 1000; n *= 10) //最大位数为三位数则100，四位数则1000 以此类推
{
int[,] tmp = new int[10, size];
for (int i = 0; i < size; i++)
{
int m = (arrays[i] / n) % 10;
tmp[m, i] = arrays[i];
}
int k = 0;
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < size; j++)
{
if (tmp[i, j] != 0)
{
arrays[k] = tmp[i, j];
k++;
}
}
}
}
}
| 
转播
