各种排序算法

一条柴 · 发表于 2017-4-13 18:59:30

在Unity中可能会用到。这里为大家介绍下。

下面直接为大家贴代码：

一、归并排序

public static void MergeSort(int[] arr, int start, int end) //递归
{
if (start < end)
{
int middle = (start + end) / 2;
MergeSort(arr,start,middle);
MergeSort(arr,middle+1,end);
MergeSort(arr,start,middle,end);
}
}

public static void MergeSort(int[] arr, int start, int middle, int end)
{
int[] tmp = new int[end - start + 1];
int i = start;
int j = middle + 1;
int k = 0;

while (i <= middle && j <= end)
{
if (arr < arr[j])
{
tmp[k] = arr;
k++;
i++;
}
else
{
tmp[k] = arr[j];
k++;
j++;
}
}

while (i <= middle)
{
tmp[k] = arr;
k++;
i++;
}

while (j <= end)
{
tmp[k] = arr[j];
k++;
j++;
}

for (k = 0, i = start; i <= end; k++, i++)
arr = tmp[k];

}

二、希尔排序

public static void ShellSort(int[] arr)
{
int gap = arr.Length / 2;
int tmp;
while (gap > 0)
{
for (int i = 0; i < arr.Length; i++)
{
tmp = arr;
int j;
for(j = i-gap;j >= 0 ;j-=gap)
{
if (arr[j] > tmp)
arr[j + gap] = arr[j];
else
break;
}
arr[j + gap] = tmp;
}
gap /= 2;
}
}

三、基数排序

public static void RadixSort(int[] arr)
{
int MaxLength = 1; //最大数的位数
int tmp,num,i,j;
List<int>[] list = new List<int>[10];
for (i = 0; i < 10;i++ )
list = new List<int>();
for (i = 0; i < arr.Length; i++)
{
num = arr;
tmp = 0;
while (num != 0)
{
tmp++;
num /= 10;
}
if (tmp > MaxLength)
MaxLength = tmp;
}

for (i = 0; i < MaxLength; i++)
{
for (j = 0; j < arr.Length; j++)
{
num = arr[j];
tmp = i;
while (tmp > 0)
{
num /= 10;
tmp--;
}
tmp = num % 10; //第i+1位上的数
list[tmp].Add(arr[j]);

}
tmp = 0;
for (j = 0; j < 10; j++)
{
foreach (int k in list[j])
{
arr[tmp] = k;
tmp++;
}
list[j].Clear();
}
}
}

四、快速排序
static int Partition(int[] arr, int low, int high)
{
//进行一趟快速排序,返回中心轴记录位置
// arr[0] = arr[low];
int pivot = arr[low];//把中心轴置于arr[0]
while (low < high)
{
while (low < high && arr[high] >= pivot)
{
--high;
}
Swap(ref arr[high], ref arr[low]);//将比中心轴记录小的移到低端
while (low < high && arr[low] <= pivot)
{
++low;
}
Swap(ref arr[high], ref arr[low]);//将比中心轴记录大的移到高端

}
arr[low] = pivot; //中心轴移到正确位置
return low; //返回中心轴位置
}
static void Swap(ref int i, ref int j)
{
int t;
t = i;
i = j;
j = t;
}
static void QuickSort(int[] arr, int low, int high)
{
if (low < high )//当 arr[low,high]为空或只一个记录无需排序
{
int pivot = Partition(arr, low, high);
QuickSort(arr, low, pivot - 1);
QuickSort(arr, pivot + 1, high);

}
}

五、堆排序

public static void HeapSort(int[] arr)
{

BuildMaxHeap(arr);

for (int i = (arr.Length - 1); i > 0; i--)
{
Swap(ref arr[0], ref arr); //将堆顶原素和无序区的最后一个原素交换
MaxHeaping(arr, 0, i); //将新的无序区调整为堆
}
}

/// <summary>
/// 初始化大根堆，由底向上建堆
/// 完全二叉树的基本性质，最底层节点是n/2，所以从arr.Length/2开始
/// </summary>
private static void BuildMaxHeap(int[] arr)
{
for (int i = (arr.Length / 2) - 1; i >= 0; i--)
{
MaxHeaping(arr, i, arr.Length);
}
}

/// <summary>
/// 将指定的节点调整为堆
/// </summary>
/// <param name="i">需要调整的节点</param>
/// <param name="heapSize">堆的大小，也指数组中无序区的长度</param>
private static void MaxHeaping(int[] arr, int i, int heapSize)
{
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
int large = i; // 临时变量，存放大的节点值

// 比较左子节点
if (left < heapSize && arr[left] > arr[large])
{
large = left;
}

// 比较右子节点
if (right < heapSize && arr[right] > arr[large])
{
large = right;
}

// 如有子节点大于自身就交换，使大的原素上移
if (i != large)
{
Swap(ref arr, ref arr[large]);
MaxHeaping(arr, large, heapSize);
}
}

private static void Swap(ref int a, ref int b)
{
int tmp;
tmp = a;
a = b;
b = tmp;
}