一、冒泡排序(Bubble Sort)
算法原理
冒泡排序动画演示
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。当最后一对执行结束，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法描述
//将数组sort进行升序排序
public int[] BubbleSort(int [] sort ){
for (int i = 0; i < sort.Length-1; i++) {
for (int j = 0; j < sort.Length - 1 - i; j++) {
//判断sort[j] 与sort[j+1]比较大小，如果sort[j]>sort[j+1]则交换位置
if (sort [j] > sort [j + 1]) {
int temp = sort [j];
sort [j] = sort [j+1];
sort [j + 1] = temp;
}
}
}
return sort;
}
二、快速排序(Quick Sort)
算法原理
快速排序动画演示
- 设置两个变量left，right，排序开始的时候：left=0，right=N-1（N为数组长度）；
- 以第一个数组元素作为关键数据，赋值给key，即key=sort[0]；
- 从right开始向前搜索，即由后开始向前搜索(right--)，找到第一个小于key的值sort[right]，将sort[right]和sort[left]互换；
- 从left开始向后搜索，即由前开始向后搜索(left++)，找到第一个大于key的sort[left]，将sort[left]和sort[right]互换；
- 重复第3、4步，直到left=right； (3,4步中，没找到符合条件的值，即3中sort[right]不小于key,4中sort[left]不大于key的时候改变right、left的值，使得right=right-1，left=left+1，直至找到为止。找到符合条件的值，进行交换的时候left， right位置不变。另外，left==right这一过程一定正好是left+或right-完成的时候，此时令循环结束）。
算法描述
//将数组sort进行升序排序
public void QuickSort (ref int [] sort ,int left,int right){
//当left==right时 表示排序结束
if (left >= right) {
return;
}
int index = QuickSortUnit (ref sort ,left,right)；
QuickSort (ref sort,left,index-1);
QuickSort (ref sort,index+1,right);
}
//将下标从left到right的这段数组进行大致排序
public int QuickSortUnit (ref int [] sort ,int left,int right){
int key = sort[left];//将sort[left]赋值给key
while (left < right)
{
//找到后边第一个大于等于key的值将其与sort[left]交换
while (sort[right] >= key && right > left)
--right;
sort[left] = sort[right];
//找到前边第一个大于等于key的值将其与sort[right]交换
while (sort[left] <= key && right > left)
++left;
sort[right] = sort[left];
}
//循环结束，right = left，数组下标小于left的值小于sort[left] ，数组下标大于left的值大于sort[left]
sort[left] = key;
//返回此时的left
return right;
}
三、直接插入排序(straight insertion sort)
算法原理
插入排序动画演示
每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。
算法描述
//将数组sort进行升序排序
public int[] DirectInsertionSort (int [] sort ){
int temp;
for (int i = 1; i < sort.Length; i++) {
if (sort [i] < sort [i - 1]) {
temp = sort [i];
int j = i - 1;
//将有序数组部分大于temp的值的下标往后移一位
while (j>=0 && sort [j] > temp) {
sort [j + 1] = sort [j];
j--;
}
sort [j + 1] = temp;
}
}
return sort;
}
四、希尔排序(Shell Sort)
算法原理
希尔排序动画演示
- 取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。
- 在各组内进行直接插入排序
- 取第二个增量d2<d1重复上述的分组和排序，直至所取的增量为1即所有记录放在同一组中进行直接插入排序为止。
算法描述
public int[] ShellSort (ref int [] sort ){
int k;//设置增量
for (k = 1; k <= sort.Length / 9; k = 3 * k + 1) {
}
for (; k > 0; k = k / 3) {
//直接插入排序
for (int i = k + 1; i < sort.Length; i += k) {
int temp = sort [i - 1];
int j = i;
while (j > k && sort [j - k - 1] > temp) {
sort [j - 1] = sort [j - k - 1];
j = j - k;
}
sort [j - 1]=temp;
}
}
return sort;
}
五、直接选择排序(Straight Selection Sort)
算法原理
选择排序动画演示
- 第一次从R[0]~R[n-1]中选取最小值，与R[0]交换
- 第二次从R[1]~R[n-1]中选取最小值，与R[1]交换
- ....
- 第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换
- .....
- 第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换
- 总共通过n-1次，得到一个按排序码从小到大排列的有序序列·
算法描述
//将数组sort进行升序排序
public int[] StraightSelectSort (ref int [] sort ){
for (int i = 0; i < sort.Length-1; i++) {
int minindex = i;//默认此时下标为i的值最小
for (int j = i + 1; j < sort.Length; j++) {
if (sort [j] < sort [minindex]) {
minindex = j;//当下标为j的值小于最小值时将j复制给minIndex
}
}
//将最小值与sort[i]交换
int temp = sort [i];
sort [i] = sort [minindex];
sort [minindex] = temp;
}
return sort;
}
六、堆排序(Heap Sort)
算法原理
堆排序动画演示
- 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
- 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
- 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
- ……
- 直到无序区只有一个元素为止。
算法描述
public int[] Heapsort (ref int [] sort ){
int i, size = sort.Length;
//建一个大根堆
for(i=size-1;i>=0;i--)
{
MinHeapify(ref sort,size,i);
}
//将大根堆的根与无序数组段的最后一个元素交换
while(size>0)
{
sort[size-1]=sort[0]+(sort[0]=sort[size-1])*0;
size--;
MinHeapify(ref sort,size,0);
}
return sort;
}
//建大根堆
public void MinHeapify(ref int [] sort,int size,int element){
int lchild = element*2+1,rchild=lchild+1;
while (rchild < size) {
if(sort[element]<=sort[lchild]&&sort[element]<=sort[rchild])
return;
if (sort [lchild] <= sort [rchild]) {
sort [element] = sort [lchild] + (sort [lchild] = sort [element]) * 0;
element = lchild;
} else {
sort [element] = sort [rchild] + (sort [rchild] = sort [element]) * 0;
element = rchild;
}
lchild=element*2+1;
rchild=lchild+1;
}
}
七、归并排序(Merge Sort)
算法原理
归并排序动画演示
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针超出序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
算法描述
public int[] MergeSort(ref int [] sort,ref int [] array,int startIndex,int endIndex ){
int midIndex;
if(startIndex < endIndex)
{
midIndex = (startIndex + endIndex) / 2;
MergeSort(ref sort, ref array, startIndex, midIndex);
MergeSort(ref sort, ref array, midIndex+1, endIndex);
Merge(ref sort, ref array, startIndex, midIndex, endIndex);
}
return sort;
}
public void Merge(ref int[] sort,ref int[] array, int startIndex, int midIndex, int endIndex)
{
int i = startIndex, j=midIndex+1, k = startIndex;
while(i!=midIndex+1 && j!=endIndex+1)
{
if(sort[i] > sort[j])
array[k++] = sort[j++];
else
array[k++] = sort[i++];
}
while(i != midIndex+1)
array[k++] = sort[i++];
while(j != endIndex+1)
array[k++] = sort[j++];
for(i=startIndex; i<=endIndex; i++)
sort[i] = array[i];
} 