归并、冒泡、选择、快速、计数、基数
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace Sort
{
public class MergeSort
{
public void Merge(ref int[] aa, int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int k = 1, i = 0, j = 0;
int[] l=new int [n1+1];
int[] R=new int [n2+1];
for (i = 1; i <= n1; i++)
{
l[i] = aa[p + i-1];
}
for (i = 1; i <= n2; i++)
{
R[i]=aa[q+i];
}
i = 1; j = 1; k = p;
while (i <=n1 && j <=n2)
{
if (l[i] < R[j])
aa[k++] = l[i++];
else
aa[k++] = R[j++];
}
if (i > n1)
{
while (j <= n2)
{
aa[k++] = R[j++];
}
}
else
{
while (i <= n1)
{
aa[k++] = l[i++];
}
}
}
public void Sort(ref int[] aa, int p, int r)
{
if (p < r)
{
int q = (p + r) / 2;
Sort(ref aa,p,q);
Sort(ref aa,q+1,r);
Merge(ref aa,p,q,r);
}
}
}
public class HeapSort
{
public void MaxHeapify(ref int[] a, int i, int length)
{
int l = i * 2;
int r = i * 2 + 1;
int largest;
if (l <= length && a[l] > a[i])
largest = l;
else
largest = i;
if (r <= length && a[r] > a[largest])
largest = r;
if (largest != i)
{
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
MaxHeapify(ref a, largest, length);
}
}
public void BuildMaxHeap(ref int[] a)
{
for (int i = a.Length - 1; i > = 1; i--)
{
MaxHeapify(ref a, i, a.Length - 1);
}
}
public void Sort(ref int[] a)
{
BuildMaxHeap(ref a);
for (int i = a.Length - 1; i > 1; i--)
{
int temp;
temp = a[1];
a[1] = a[i];
a[i] = temp;
MaxHeapify(ref a, 1, i - 1);
}
}
}
public class BubleSort
{
public void Sort(ref int[] a)
{
int n=a.Length-1;
for (int i = 1; i < n; i++)
{
for (int j = 1; j <= n - i; j++)
{
if (a[j+1] > a[j])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
}
public class SelectSort
{
public void Sort(ref int[] a)
{
int n=a.Length-1;
int max;
int maxIndex;
for (int i = 1; i < n; i++)
{
max = a[i];
maxIndex = i;
for (int j = i+1; j <= n; j++)
{
if (a[j] > max)
{
max = a[j]; maxIndex = j;
}
}
if (maxIndex != i)
{
a[maxIndex] = a[i];
a[i] = max;
}
}
}
}
public class QuickSort
{
Random rd = new Random();
public delegate int Partion(int[] a,int p,int r);
public void QSort(ref int[] a,int p,int r,Partion partition)
{
if (p < r)
{
int q = partition(a,p,r);
QSort(ref a,p,q-1,partition);
QSort(ref a, q + 1, r,partition);
}
}
private void QSort(ref int[] a, int p, int p_3)
{
throw new Exception( "The method or operation is not implemented. ");
}
public int PartitionSingle(int[] a, int p, int r)
{
int i = rd.Next(p, r);
int temp = a[i];
a[i] = a[r]; a[r] = temp;
int x = a[r];
i = p - 1;
for (int j = p; j < r; j++)
{
if (a[j] < x)
{
i++;
temp = a[i]; a[i] = a[j]; a[j] = temp;
}
}
temp = a[i + 1]; a[i + 1] = a[r]; a[r] = temp;
return i + 1;
}
public int PartitionDouble(int[] a, int p, int r)
{
int i=rd.Next(p, r);
int temp = a[i];
a[i] = a[r]; a[r] = temp;
int x = a[r];
while (p < r)
{
while (p < r && a[p] <= x) p++;
if (p < r)
{
a[r] = a[p]; r--;
}
while (p < r && a[r] > = x) r--;
if (p < r)
{
a[p] = a[r]; p++;
}
}
a[p] = x;
return p;
}
public void Sort(ref int[] a)
{
Console.Write( "pleale select partition of method: 1 is single and 2 is double> ");
int userInput = Convert.ToInt32(Console.ReadLine());
if (userInput == 1)
QSort(ref a, 1, a.Length - 1, PartitionSingle);
else if (userInput == 2)
QSort(ref a, 1, a.Length - 1, PartitionDouble);
}
}
|
