交换类排序
冒泡排序精髓：
设置一个两层循环。外层遍历次数为比较次数，内层从前往后遍历所有元素，当前者大于后者则交换位置。
public void BubbleSort(int[] a)
{
int temp, upper = a.Length-1;
for (int outer =1; outer<=upper; outer++)
{
//每完成一次外层遍历，最大的肯定在最后,所以少遍历outer个元素
for (int inner = 0; inner <= upper-outer; inner++)
{
if (arr[inner] > arr[inner + 1])
{
temp = arr[inner];
arr[inner] = arr[inner + 1];
arr[inner + 1] = temp;
}
}
}
}
#快速排序精髓（分治）
将数组递归划分成两个子序列:设置pivot值，小于pivot的在pivot左边，大的在pivot右边。最先暂存的pivot值是为了给交换数值腾出位置，比较完后就附给中间值，因为比较都是以pivot来分大小，排左右的。
public void QuickSort(int[] a,int low, int upper)
{
if (low< upper)
{
int pivotIndex = Partition(a, low, upper);
//利用分之思想，将问题分成小块
QuickSort(a, low, pivotIndex- 1);
QuickSort(a, pivotIndex+ 1, upper);
}
}
//划分子序列
private int Partition(int[] a, int low, int upper)
{
int pivot = a[low]; //low作为比较的起点，暂存一下中轴值
while (low< upper)//从两端交替向内扫描
{
//low指针不动，upper指针扫描low右边
while (low< upper&& a[upper] >= pivot)
upper--;
a[low] = a[upper];//将比pivot小的元素移向低端
//upper指针不动，low指针扫描upper左边
while (upper>low&& a[low] <= pivot)
low++;
a[upper] = a[low];//将比pivot大的元素移到高端
}
//low==high
a[low] = pivot; //将中轴元素附给中间这个位置
return low; //返回轴元素
}
处理大数据量且无序的排序问题，快速排序是最快的。.Net 框架库类中的 Sort 方法就是用快速排序算法实现的。另外，快排中的第一个pivot最好由arr[(int)arr.GetUpperBound(0) / 2]来确定（除非数组随机无序）
选择类排序
简单选择排序精髓
设置两层循环。外层遍历所有元素，内层遍历外层之后元素，找到其中最小元素记录，然后和当前外层元素交换。
public void SelectionSort(int[] a)
{
//O(N^2+N)
int minIndex, temp, upper = a.Length-1;
//遍历次数
for (int outer = 0; outer <= upper; outer++)
{
minIndex = outer;
//找到最小值索引
for (int inner = outer + 1; inner <= upper; inner++)
{
if (arr[inner] < arr[minIndex])
minIndex = inner;
}
//交换
temp = arr[outer];
arr[outer] = arr[minIndex];
arr[minIndex] = temp;
// DisplayElements();
}
}
插入类排序
直接插入排序精髓
把数组分为排好序的和没排好序的两半。设置两层循环，外层遍历第二个元素开始的所有元素，内层遍历排好序的元素。外层遍历元素在排序好的数中找位置：从后往前查找大于本身数直到有数小于本身，插入该位置。
public void InsertSort(int[] a)
{
//O(N^2)
int temp, inner;
//遍历次数，从第二个数开始检查,第一个数默认有序
for (int outer = 1; outer <= upper; outer++)
{
temp = arr[outer];
inner = outer;
while (inner > 0 && arr[inner - 1] >= temp) //数据后移
{
arr[inner] = arr[inner - 1];
inner -= 1;
}
arr[inner] = temp;
//DisplayElements();
}
}
折半插入排序精髓
在直接插入排序的基础上，有效的减少比较次数，但是移动次数并不会改变。设置两重循环，外层循环遍历第二个元素开始的所有数据，内层设置两个同级循环，一个用来折半遍历；另一个用来移动数据。
public void BinInsertSort()
{
//所有待排序元素
for (int i = 1; i <= upper; i++)
{
int temp = arr[i];
//前面有序子序列的范围
int hi = i - 1;int lo = 0;
while (lo <= hi) //折半定位
{
int half = (lo + hi) / 2;
if (arr[half] < temp)
lo = half + 1;
else
hi = half - 1;
}
for (int j = i - 1; j > hi; j--)//移动
arr[j + 1] = arr[j];
arr[hi + 1] = temp; //插入
}
// DisplayElements();
}
希尔排序（直接插入排序改进版）
将待排序的元素分为多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入排序。本算法的关键内容是对远距离而非相邻的数据项进行比较。当算法循环遍历数据集合的时候，每个数据项间的距离会缩短，直到算法对相邻数据项进行比较时才终止。
public void ShellSort()
{
int inner, temp;
int h = 3; //步长
while (h > 0)
{
for (int outer = h; outer <= upper; outer++)
{
temp = arr[outer];
inner = outer;
while ((inner > h - 1) && arr[inner - h] >= temp)
{
arr[inner] = arr[inner - h];
inner -= h;
}
arr[inner] = temp;
}
h = (h - 1) % 3; //缩短步长再次排序
}
//DisplayElements();
}
直接插入排序适合数据量少的情况下，后两个适合数据量大的的情况。同时，折半查找只是减少了比较次数、复杂度并没有降低。而希尔排序的复杂度受步长影响
分治类排序（递归）
1.快速排序（转上）
2.归并排序
这个算法把数据集合不断的分成两个部分，然后对每部分递归地进行
排序。当两个部分都排序好时，再用合并程序把它们组合在一起。
但是归并排序需要注意一个问题就是：划分出来的两个部分不一样长。这就要做一个规定：当主循环结束后，当且仅当两个数组中的一个数组还有元素时，可以使用两个额外的循环。
/// <summary>
/// 归并排序,分治法
/// </summary>
public void MergeSort()
{
//创建一个暂存数组,避免合并时反复申请内存
int[] t = new int[arr.Length];
Sort(arr,t, 0, arr.Length - 1);
DisplayElements();
}
//递归排序
public static void Sort(int[] a, int[] t, int low, int high)
{
if (low < high)
{
//划分待排序列
int mid = (low + high) / 2;
Sort(a,t, low, mid);
Sort(a,t, mid + 1, high);
//合并
Merge(a,t, low, mid, high);
}
}
private static void Merge(int[] a, int[] t,int low, int mid, int high)
{
//m左序列起始指针，n右序列起始指针，k暂存数组起始指针
int m = low, n = mid + 1, k = low;
//比较左右两个序列上指针指的数字大小，小的先入数组
while (n <= high && m <= mid)
{
if (a[m] > a[n])
t[k++] = a[n++];
else
t[k++] = a[m++];
}
//如果两个子序列中有一个子序列先合并完了，把剩下的子序列全部加入暂存数组中
//左序列还有剩下的
while (n < high + 1)
t[k++] = a[n++];
//右序列还有剩下的
while (m < mid + 1)
t[k++] = a[m++];
//把暂存数组里的数据再导回原来数组中
for (int i = low; i <= high; i++)
a[i] = t[i];
}
为了形象化理解，参看图示：
图示
对比
网友评论