Bubble Sort冒泡排序
Selection Sort选择排序
Insertion Sort插入排序
Quick Sort快速排序
Shell Sort 希尔排序
Merge Sort 归并排序
Heap Sort 堆排序
Bucket Sort 桶排序又叫箱排序
Radix Sort 基数排序
Count Sort 计数排序
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
/// 冒泡排序 Bubble Sort
/// </summary>
public static class BubbleSort
{
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
public static void Sort<T>(T[] array) where T : IComparable
{
for (int i = 0; i < array.Length; i++)
{
bool isAnyChange = false;
for (int j = 0; j < array.Length - 1; j++)
{
if (array[j].CompareTo(array[j + 1]) > 0)
{
isAnyChange = true;
Swap(array, j, j + 1);
}
}
if (!isAnyChange)
{
break;
}
}
}
/// <summary>
/// 泛型
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="first"></param>
/// <param name="second"></param>
private static void Swap<T>(T[] array, int first, int second)
{
T temp = array[first];
array[first] = array[second];
array[second] = temp;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
/// Bucket Sort 桶排序又叫箱排序
/// </summary>
public class BucketSort
{
//Bucket sort breaks a list down into sub-lists, you can then use another algo to sort the sub-lists
//Bucketsort isn't a good choice if you don't know the range or distribution of the data
//Bucket Sort time complexity
//Average case: O(n+k) - k being the number of buckets that were created
//Worst case: O(N^2)
//In this case, we will focus on building an algorithm that uses bucketsort to sort an array of integers between 1 and 99
//we will also assume that the integers in the passed array are evenly distributed
public static List<int> bucketSort(params int[] x)
{
List<int> result = new List<int>();
//Determine how many buckets you want to create, in this case, the 10 buckets will each contain a range of 10
//1-10, 11-20, 21-30, etc. since the passed array is between 1 and 99
int numOfBuckets = 10;
//Create buckets
List<int>[] buckets = new List<int>[numOfBuckets];
for (int i = 0; i < numOfBuckets; i++)
buckets[i] = new List<int>();
//Iterate through the passed array and add each integer to the appropriate bucket
for (int i = 0; i < x.Length; i++)
{
int buckitChoice = (x[i] / numOfBuckets);
buckets[buckitChoice].Add(x[i]);
}
//Sort each bucket and add it to the result List
//Each sublist is sorted using Bubblesort, but you could substitute any sorting algo you would like
for (int i = 0; i < numOfBuckets; i++)
{
int[] temp = BubbleSortList(buckets[i]);
result.AddRange(temp);
}
return result;
}
//Bubblesort w/ ListInput
/// <summary>
///
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public static int[] BubbleSortList(List<int> input)
{
for (int i = 0; i < input.Count; i++)
{
for (int j = 0; j < input.Count; j++)
{
if (input[i] < input[j])
{
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
}
return input.ToArray();
}
////Call in Program.cs to test
//int[] x = new int[] { 99, 95, 90, 85, 80, 75, 70, 65, 60, 55, 50, 45, 40, 35, 30, 25, 20, 15, 10, 5, 1 };
//List<int> sorted = Bucket_Sort.BucketSort(x);
//foreach (int i in sorted)
// Console.WriteLine(i);
/// <summary>
///
/// </summary>
/// <param name="data"></param>
/// <param name="bucketCount"></param>
public static void DBBucketSort(double[] data, int bucketCount)
{
var buckets = new List<double>[bucketCount];
for (int i = 0; i < bucketCount; i++)
buckets[i] = new List<double>(data.Length / bucketCount);
var min = double.MaxValue;
var max = -double.MaxValue;
for (int i = 0; i < data.Length; i++)
{
min = Math.Min(min, data[i]);
max = Math.Max(max, data[i]);
}
for (int i = 0; i < data.Length; i++)
{
var idx = Math.Min(bucketCount - 1, (int)(bucketCount * (data[i] - min) / (max - min)));
buckets[idx].Add(data[i]);
}
Parallel.For(0, bucketCount, i => buckets[i].Sort());
var index = 0;
for (var i = 0; i < bucketCount; i++)
for (var j = 0; j < buckets[i].Count; j++)
data[index++] = buckets[i][j];
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
/// Count Sort 计数排序
/// </summary>
public class CountSort
{
/// <summary>
///
/// </summary>
/// <param name="array"></param>
/// <returns></returns>
public int[] CountingSort(int[] array)
{
var size = array.Length;
var maxElement = GetMaxVal(array, size);
var occurrences = new int[maxElement + 1];
for (int i = 0; i < maxElement + 1; i++)
{
occurrences[i] = 0;
}
for (int i = 0; i < size; i++)
{
occurrences[array[i]]++;
}
for (int i = 0, j = 0; i <= maxElement; i++)
{
while (occurrences[i] > 0)
{
array[j] = i;
j++;
occurrences[i]--;
}
}
return array;
}
/// <summary>
///
/// </summary>
/// <param name="array"></param>
/// <param name="size"></param>
/// <returns></returns>
public static int GetMaxVal(int[] array, int size)
{
var maxVal = array[0];
for (int i = 1; i < size; i++)
if (array[i] > maxVal)
maxVal = array[i];
return maxVal;
}
/// <summary>
///
/// </summary>
/// <param name="arr"></param>
/// <exception cref="IndexOutOfRangeException"></exception>
public static void duCountSort(int[] arr)
{
int max = -1;
foreach (int i in arr)
{
if (i < 0)
{
throw new IndexOutOfRangeException(" < 0 ");
}
max = Math.Max(max, i);
}
int n = arr.Length;
// The output character array that will have sorted arr
int[] output = new int[n];
// Create a count array to store count of inidividul
// characters and initialize count array as 0
int[] count = new int[max + 1];
for (int i = 0; i <= max; ++i)
count[i] = 0;
// store count of each character
foreach (int i in arr)
count[i]++;
// Change count[i] so that count[i] now contains actual
// position of this character in output array
for (int i = 1; i <= max; ++i)
count[i] += count[i - 1];
// Build the output character array
for (int i = 0; i < n; ++i)
{
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// Copy the output array to arr, so that arr now
// contains sorted characters
for (int i = 0; i < n; ++i)
arr[i] = output[i];
}
/// <summary>
///
/// </summary>
/// <param name="arr"></param>
public static void countsortstr(char[] arr)
{
int n = arr.Length;
// The output character array that
// will have sorted arr
char[] output = new char[n];
// Create a count array to store
// count of individual characters
// and initialize count array as 0
int[] count = new int[256];
for (int i = 0; i < 256; ++i)
count[i] = 0;
// store count of each character
for (int i = 0; i < n; ++i)
++count[arr[i]];
// Change count[i] so that count[i]
// now contains actual position of
// this character in output array
for (int i = 1; i <= 255; ++i)
count[i] += count[i - 1];
// Build the output character array
// To make it stable we are operating in reverse
// order.
for (int i = n - 1; i >= 0; i--)
{
output[count[arr[i]] - 1] = arr[i];
--count[arr[i]];
}
// Copy the output array to arr, so
// that arr now contains sorted
// characters
for (int i = 0; i < n; ++i)
arr[i] = output[i];
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
///Heap Sort 堆排序
///
/// </summary>
public class HeapSort
{
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
public static void heapSort<T>(T[] array) where T : IComparable<T>
{
int heapSize = array.Length;
buildMaxHeap(array);
for (int i = heapSize - 1; i >= 1; i--)
{
swap(array, i, 0);
heapSize--;
sink(array, heapSize, 0);
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
private static void buildMaxHeap<T>(T[] array) where T : IComparable<T>
{
int heapSize = array.Length;
for (int i = (heapSize / 2) - 1; i >= 0; i--)
{
sink(array, heapSize, i);
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="heapSize"></param>
/// <param name="toSinkPos"></param>
private static void sink<T>(T[] array, int heapSize, int toSinkPos) where T : IComparable<T>
{
if (getLeftKidPos(toSinkPos) >= heapSize)
{
// No left kid => no kid at all
return;
}
int largestKidPos;
bool leftIsLargest;
if (getRightKidPos(toSinkPos) >= heapSize || array[getRightKidPos(toSinkPos)].CompareTo(array[getLeftKidPos(toSinkPos)]) < 0)
{
largestKidPos = getLeftKidPos(toSinkPos);
leftIsLargest = true;
}
else
{
largestKidPos = getRightKidPos(toSinkPos);
leftIsLargest = false;
}
if (array[largestKidPos].CompareTo(array[toSinkPos]) > 0)
{
swap(array, toSinkPos, largestKidPos);
if (leftIsLargest)
{
sink(array, heapSize, getLeftKidPos(toSinkPos));
}
else
{
sink(array, heapSize, getRightKidPos(toSinkPos));
}
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="pos0"></param>
/// <param name="pos1"></param>
private static void swap<T>(T[] array, int pos0, int pos1)
{
T tmpVal = array[pos0];
array[pos0] = array[pos1];
array[pos1] = tmpVal;
}
/// <summary>
///
/// </summary>
/// <param name="parentPos"></param>
/// <returns></returns>
private static int getLeftKidPos(int parentPos)
{
return (2 * (parentPos + 1)) - 1;
}
/// <summary>
///
/// </summary>
/// <param name="parentPos"></param>
/// <returns></returns>
private static int getRightKidPos(int parentPos)
{
return 2 * (parentPos + 1);
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
public static void printArray<T>(T[] array)
{
foreach (T t in array)
{
Console.Write(' ' + t.ToString() + ' ');
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
/// 插入排序Insertion Sort
/// </summary>
public static class InsertionSort
{
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
public static void Sort<T>(T[] array) where T : IComparable
{
for (int i = 1; i < array.Length; i++)
{
int j = i;
while (j > 0 && array[j].CompareTo(array[j - 1]) < 0)
{
Swap(array, j, j - 1);
j--;
}
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="first"></param>
/// <param name="second"></param>
private static void Swap<T>(T[] array, int first, int second)
{
T temp = array[first];
array[first] = array[second];
array[second] = temp;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
/// Merge Sort 归并排序
/// </summary>
public class MergeSort
{
/// <summary>
///
/// </summary>
/// <param name="array"></param>
/// <returns></returns>
public static int[] mergeSort(int[] array)
{
int[] left;
int[] right;
int[] result = new int[array.Length];
//As this is a recursive algorithm, we need to have a base case to
//avoid an infinite recursion and therfore a stackoverflow
if (array.Length <= 1)
return array;
// The exact midpoint of our array
int midPoint = array.Length / 2;
//Will represent our 'left' array
left = new int[midPoint];
//if array has an even number of elements, the left and right array will have the same number of
//elements
if (array.Length % 2 == 0)
right = new int[midPoint];
//if array has an odd number of elements, the right array will have one more element than left
else
right = new int[midPoint + 1];
//populate left array
for (int i = 0; i < midPoint; i++)
left[i] = array[i];
//populate right array
int x = 0;
//We start our index from the midpoint, as we have already populated the left array from 0 to midpont
for (int i = midPoint; i < array.Length; i++)
{
right[x] = array[i];
x++;
}
//Recursively sort the left array
left = mergeSort(left);
//Recursively sort the right array
right = mergeSort(right);
//Merge our two sorted arrays
result = merge(left, right);
return result;
}
//This method will be responsible for combining our two sorted arrays into one giant array
/// <summary>
///
/// </summary>
/// <param name="left"></param>
/// <param name="right"></param>
/// <returns></returns>
public static int[] merge(int[] left, int[] right)
{
int resultLength = right.Length + left.Length;
int[] result = new int[resultLength];
//
int indexLeft = 0, indexRight = 0, indexResult = 0;
//while either array still has an element
while (indexLeft < left.Length || indexRight < right.Length)
{
//if both arrays have elements
if (indexLeft < left.Length && indexRight < right.Length)
{
//If item on left array is less than item on right array, add that item to the result array
if (left[indexLeft] <= right[indexRight])
{
result[indexResult] = left[indexLeft];
indexLeft++;
indexResult++;
}
// else the item in the right array wll be added to the results array
else
{
result[indexResult] = right[indexRight];
indexRight++;
indexResult++;
}
}
//if only the left array still has elements, add all its items to the results array
else if (indexLeft < left.Length)
{
result[indexResult] = left[indexLeft];
indexLeft++;
indexResult++;
}
//if only the right array still has elements, add all its items to the results array
else if (indexRight < right.Length)
{
result[indexResult] = right[indexRight];
indexRight++;
indexResult++;
}
}
return result;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
/// 快捷排序 Quick Sort
/// </summary>
public static class QuickSort
{
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
public static void Sort<T>(T[] array) where T : IComparable
{
Sort(array, 0, array.Length - 1);
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="lower"></param>
/// <param name="upper"></param>
private static void Sort<T>(T[] array, int lower, int upper) where T : IComparable
{
if (lower < upper)
{
int p = Partition(array, lower, upper);
Sort(array, lower, p);
Sort(array, p + 1, upper);
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="lower"></param>
/// <param name="upper"></param>
/// <returns></returns>
private static int Partition<T>(T[] array, int lower, int upper) where T : IComparable
{
int i = lower;
int j = upper;
T pivot = array[lower];
// T pivot = array[(lower + upper) / 2];
do
{
while (array[i].CompareTo(pivot) < 0) { i++; }
while (array[j].CompareTo(pivot) > 0) { j--; }
if (i >= j) { break; }
Swap(array, i, j);
}
while (i <= j);
return j;
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="first"></param>
/// <param name="second"></param>
private static void Swap<T>(T[] array, int first, int second)
{
T temp = array[first];
array[first] = array[second];
array[second] = temp;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
/// Radix Sort 基数排序
/// </summary>
public class RadixSort
{
/// <summary>
///
/// </summary>
/// <param name="arr"></param>
public static void radixSort(int[] arr)
{
int i, j;
int[] tmp = new int[arr.Length];
for (int shift = 31; shift > -1; --shift)
{
j = 0;
for (i = 0; i < arr.Length; ++i)
{
bool move = (arr[i] << shift) >= 0;
if (shift == 0 ? !move : move)
arr[i - j] = arr[i];
else
tmp[j++] = arr[i];
}
Array.Copy(tmp, 0, arr, arr.Length - j, j);
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
/// 选择排序 Selection Sort
/// </summary>
public static class SelectionSort
{
/// <summary>
/// /
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
public static void Sort<T>(T[] array) where T : IComparable
{
for (int i = 0; i < array.Length - 1; i++)
{
int minIndex = i;
T minValue = array[i];
for (int j = i + 1; j < array.Length; j++)
{
if (array[j].CompareTo(minValue) < 0)
{
minIndex = j;
minValue = array[j];
}
}
Swap(array, i, minIndex);
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="first"></param>
/// <param name="second"></param>
private static void Swap<T>(T[] array, int first, int second)
{
T temp = array[first];
array[first] = array[second];
array[second] = temp;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
/// Shell Sort 希尔排序
/// </summary>
public class ShellSort
{
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
public static void Sort<T>(IList<T> list) where T : IComparable
{
int n = list.Count;
int h = 1;
while (h < (n >> 1))
{
h = (h << 1) + 1;
}
while (h >= 1)
{
for (int i = h; i < n; i++)
{
int k = i - h;
for (int j = i; j >= h && list[j].CompareTo(list[k]) < 0; k -= h)
{
T temp = list[j];
list[j] = list[k];
list[k] = temp;
j = k;
}
}
h >>= 1;
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="first"></param>
/// <param name="second"></param>
private static void Swap<T>(T[] array, int first, int second)
{
T temp = array[first];
array[first] = array[second];
array[second] = temp;
}
/// <summary>
///
/// </summary>
/// <param name="arr"></param>
/// <param name="n"></param>
public static void IntShellSort(int[] arr, int n)
{
int i, j, pos, temp;
pos = 3;
while (pos > 0)
{
for (i = 0; i < n; i++)
{
j = i;
temp = arr[i];
while ((j >= pos) && (arr[j - pos] > temp))
{
arr[j] = arr[j - pos];
j = j - pos;
}
arr[j] = temp;
}
if (pos / 2 != 0)
pos = pos / 2;
else if (pos == 1)
pos = 0;
else
pos = 1;
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
public void InsertionSort<T>(T[] a) where T : IComparable
{
for (int i = 0; i < a.Length; i++)
{ // Exchange a[i] with smallest entry in a[i+1...N).
int min = i; // index of minimal entr.
for (int j = i + 1; j < a.Length; j++)
{
if (Less(a[j], a[min]))
{
min = j;
}
else if (a.Length < j + 1)
{
a[j + 1] = a[j];
a[j] = a[min];
}
}
Show(a);
Exch(a, i, min);
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
public void DuShellSort<T>(T[] a) where T : IComparable
{ // Sort a[] into increasing order.
int N = a.Length;
int h = 1;
while (h < N / 3)
{
h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ..
}
while (h >= 1)
{ // h-sort the array.
for (int i = h; i < N; i++)
{ // Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... .
for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
Exch(a, j, j - h);
Show(a);
}
h = h / 3;
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
public void SelectionSort<T>(T[] a) where T : IComparable
{ // Sort a[] into increasing order.
int n = a.Length; // array length
for (int i = 0; i < n; i++)
{ // Exchange a[i] with smallest entry in a[i+1...N).
int min = i; // index of minimal entr.
for (int j = i + 1; j < n; j++)
if (Less(a[j], a[min])) min = j;
Exch(a, i, min);
Show(a);
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
/// <param name="i"></param>
/// <param name="j"></param>
private static void Exch<T>(T[] a, int i, int j) where T : IComparable
{
T t = a[i];
a[i] = a[j];
a[j] = t;
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
public void Show<T>(T[] a) where T : IComparable
{ // Print the array, on a single line.
foreach (T t in a)
{
Console.Write(t + " ");
}
Console.WriteLine();
}
/// <summary>
///
/// </summary>
/// <param name="v"></param>
/// <param name="w"></param>
/// <returns></returns>
private static bool Less(IComparable v, IComparable w)
{
return v.CompareTo(w) < 0;
}
/// <summary>
///
/// </summary>
/// <param name="a"></param>
/// <returns></returns>
public bool IsSorted(IComparable[] a)
{ // Test whether the array entries are in order.
for (int i = 1; i < a.Length; i++)
if (Less(a[i], a[i - 1])) return false;
return true;
}
}
}
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CSharpDataStructuresAlgorithms.SortingAlgorithms
{
/// <summary>
/// Bubble Sort冒泡排序
/// Selection Sort选择排序
///Insertion Sort插入排序
/// Quick Sort快速排序
///Shell Sort 希尔排序
/// Merge Sort 归并排序
///Heap Sort 堆排序
///Bucket Sort 桶排序又叫箱排序
///Radix Sort 基数排序
///Count Sort 计数排序
///Bidirectional Bubble Sort
///Bubble Sort
/// Bucket Sort
/// Comb Sort
/// Cycle Sort
/// Gnome Sort
/// Heap Sort
///Insertion Sort
///Merge Sort
///Odd-Even Sort
/// Pigeonhole Sort
/// Quick Sort
///Quick Sort with Bubble Sort
/// Selection Sort
/// Shell Sort
/// </summary>
public class SortingAlgorithmsExecute
{
/// <summary>
/// 选择排序 Selection Sort
/// </summary>
public static void SelectionTest()
{
int[] integerValues = { -11, 12, -42, 0, 1, 90, 68, 6, -9 };
SelectionSort.Sort(integerValues);
Console.WriteLine(string.Join(" | ", integerValues));
float[] floatValues = { -11.2f, 12.56f, -42.59f, 0.0f, 1.1f, 90.9f, 68.68f, 6.1f, -9.8f };
SelectionSort.Sort(floatValues);
Console.WriteLine(string.Join(" | ", floatValues));
string[] stringValues = { "Mary", "Marcin", "Ann", "GeovinDu", "George", "Nicole","涂聚文","江志文","刘慧" };
SelectionSort.Sort(stringValues);
Console.WriteLine(string.Join(" | ", stringValues));
}
/// <summary>
/// 插入排序Insertion Sort
/// </summary>
public static void InsertionTest()
{
int[] integerValues = { -11, 12, -42, 0, 1, 90, 68, 6, -9 };
InsertionSort.Sort(integerValues);
Console.WriteLine(string.Join(" | ", integerValues));
float[] floatValues = { -11.2f, 12.56f, -42.59f, 0.0f, 1.1f, 90.9f, 68.68f, 6.1f, -9.8f };
InsertionSort.Sort(floatValues);
Console.WriteLine(string.Join(" | ", floatValues));
string[] stringValues = { "Mary", "Marcin", "Ann", "James", "GeovinDu", "Nicole", "涂聚文", "江志文", "刘慧" };
InsertionSort.Sort(stringValues);
Console.WriteLine(string.Join(" | ", stringValues));
}
/// <summary>
/// 冒泡排序 Bubble Sort
/// </summary>
public static void BubbleTest()
{
int[] integerValues = { -11, 12, -42, 0, 1, 90, 68, 6, -9 };
BubbleSort.Sort(integerValues);
Console.WriteLine(string.Join(" | ", integerValues));
float[] floatValues = { -11.2f, 12.56f, -42.59f, 0.0f, 1.1f, 90.9f, 68.68f, 6.1f, -9.8f };
BubbleSort.Sort(floatValues);
Console.WriteLine(string.Join(" | ", floatValues));
string[] stringValues = { "Mary", "Marcin", "Ann", "James", "GeovinDu", "Nicole", "涂聚文", "江志文", "刘慧" };
BubbleSort.Sort(stringValues);
Console.WriteLine(string.Join(" | ", stringValues));
}
/// <summary>
/// 快捷排序 Quick Sort
/// </summary>
public static void QuicksortTest()
{
int[] integerValues = { -11, 12, -42, 0, 1, 90, 68, 6, -9 };
QuickSort.Sort(integerValues);
Console.WriteLine(string.Join(" | ", integerValues));
float[] floatValues = { -11.2f, 12.56f, -42.59f, 0.0f, 1.1f, 90.9f, 68.68f, 6.1f, -9.8f };
QuickSort.Sort(floatValues);
Console.WriteLine(string.Join(" | ", floatValues));
string[] stringValues = { "Mary", "Marcin", "Ann", "James", "GeovinDu", "Nicole", "涂聚文", "江志文", "刘慧" };
QuickSort.Sort(stringValues);
Console.WriteLine(string.Join(" | ", stringValues));
}
/// <summary>
/// 希尔排序
/// </summary>
public static void ShellSortTest()
{
int[] arr = new int[] { 56, 12, 99, 32, 1, 95, 25, 5, 100, 84 };
int n = arr.Length;
int i;
Console.WriteLine("Shell Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++)
{
Console.Write(arr[i] + " ");
}
ShellSort.IntShellSort(arr, n);
Console.Write("Sorted Array is: ");
for (i = 0; i < n; i++)
{
Console.Write(arr[i] + " ");
}
}
/// <summary>
/// 归并排序
/// </summary>
public static void MergeSortTest()
{
int[] mykeys = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };
int[] myvalues = MergeSort.mergeSort(mykeys);
int n=myvalues.Length;
int i;
for (i = 0; i < n; i++)
{
Console.Write(myvalues[i] + " ");
}
}
/// <summary>
/// 堆排序
/// </summary>
public static void HeapSortTest()
{
int[] mykeys = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };
double[] doublemykeys = new double[] {2.22, 0.5, 2.7, -1.0, 11.2};
string[] stringmykeys = new string[] {"Red", "White", "Black", "geovindu", "Orange", "涂聚文", "江志文", "刘慧" };
Console.WriteLine("\nOriginal Array Elements :");
HeapSort.printArray(mykeys);
HeapSort.heapSort(mykeys);
Console.WriteLine("\n\nSorted Array Elements :");
HeapSort.printArray(mykeys);
Console.WriteLine("\n");
HeapSort.heapSort(doublemykeys);
Console.WriteLine("\n\nSorted Array Elements :");
HeapSort.printArray(doublemykeys);
Console.WriteLine("\n");
HeapSort.heapSort(stringmykeys);
Console.WriteLine("\n\nSorted Array Elements :");
HeapSort.printArray(stringmykeys);
}
/// <summary>
/// 桶排序又叫箱排序
/// </summary>
public static void BucketSortTest()
{
int[] x = new int[] { 99, 95, 90, 85, 80, 75, 70, 65, 60, 55, 50, 45, 40, 35, 30, 25, 20, 15, 10, 5, 1 };
List<int> sorted = BucketSort.bucketSort(x);
foreach (int i in sorted)
Console.WriteLine(" " + i);
}
/// <summary>
/// 基数排序
/// </summary>
public static void RadixSortTest()
{
int[] arr = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };
Console.WriteLine("\nOriginal array : ");
foreach (var item in arr)
{
Console.Write(" " + item);
}
RadixSort.radixSort(arr);
Console.WriteLine("\nSorted array : ");
foreach (var item in arr)
{
Console.Write(" " + item);
}
Console.WriteLine("\n");
}
/// <summary>
/// 计数排序
/// </summary>
public static void CountSortTest()
{
char[] arr = { 'g', 'e', 'o', 'v', 'i', 'n', 'd',
'u', 'l', 'o', 'v', 'e', 'I' };
CountSort.countsortstr(arr);
Console.Write("Sorted character array is ");
for (int i = 0; i < arr.Length; ++i)
Console.Write(" " + arr[i]);
}
/// <summary>
///
/// </summary>
/// <param name="header"></param>
/// <param name="addLine"></param>
public static void WriteHeader(string header, bool addLine = true)
{
Console.ForegroundColor = ConsoleColor.White;
Console.WriteLine((addLine ? Environment.NewLine : string.Empty) + header);
Console.ForegroundColor = ConsoleColor.Gray;
}
}
}
调用：
//geovindu
SortingAlgorithmsExecute.WriteHeader("Selection Sort 查找排序：", false);
SortingAlgorithmsExecute.SelectionTest();
SortingAlgorithmsExecute.WriteHeader("Insertion Sort 插入排序：");
SortingAlgorithmsExecute.InsertionTest();
SortingAlgorithmsExecute.WriteHeader("Bubble Sort 冒泡排序");
SortingAlgorithmsExecute.BubbleTest();
SortingAlgorithmsExecute.WriteHeader("Quick Sort 快速排序");
SortingAlgorithmsExecute.QuicksortTest();
SortingAlgorithmsExecute.WriteHeader("Merge Sort 归并排序");
SortingAlgorithmsExecute.MergeSortTest();
SortingAlgorithmsExecute.WriteHeader("Bucket Sort 桶排序又叫箱排序");
SortingAlgorithmsExecute.BucketSortTest();
SortingAlgorithmsExecute.WriteHeader("Shell Sort 希尔排序");
SortingAlgorithmsExecute.ShellSortTest();
SortingAlgorithmsExecute.WriteHeader("Heap Sort 堆排序");
SortingAlgorithmsExecute.HeapSortTest();
SortingAlgorithmsExecute.WriteHeader("Radix Sort 基数排序");
SortingAlgorithmsExecute.RadixSortTest();
SortingAlgorithmsExecute.WriteHeader("Count Sort 计数排序");
SortingAlgorithmsExecute.CountSortTest();
输出：
Selection Sort 查找排序： -42 | -11 | -9 | 0 | 1 | 6 | 12 | 68 | 90 -42.59 | -11.2 | -9.8 | 0 | 1.1 | 6.1 | 12.56 | 68.68 | 90.9 江志文 | 刘慧 | 涂聚文 | Ann | George | GeovinDu | Marcin | Mary | Nicole Insertion Sort 插入排序： -42 | -11 | -9 | 0 | 1 | 6 | 12 | 68 | 90 -42.59 | -11.2 | -9.8 | 0 | 1.1 | 6.1 | 12.56 | 68.68 | 90.9 江志文 | 刘慧 | 涂聚文 | Ann | GeovinDu | James | Marcin | Mary | Nicole Bubble Sort 冒泡排序 -42 | -11 | -9 | 0 | 1 | 6 | 12 | 68 | 90 -42.59 | -11.2 | -9.8 | 0 | 1.1 | 6.1 | 12.56 | 68.68 | 90.9 江志文 | 刘慧 | 涂聚文 | Ann | GeovinDu | James | Marcin | Mary | Nicole Quick Sort 快速排序 -42 | -11 | -9 | 0 | 1 | 6 | 12 | 68 | 90 -42.59 | -11.2 | -9.8 | 0 | 1.1 | 6.1 | 12.56 | 68.68 | 90.9 江志文 | 刘慧 | 涂聚文 | Ann | GeovinDu | James | Marcin | Mary | Nicole Merge Sort 归并排序 -4 0 2 5 6 11 18 22 51 67 Bucket Sort 桶排序又叫箱排序 1 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 99 Shell Sort 希尔排序 Shell Sort Initial array is: 56 12 99 32 1 95 25 5 100 84 Sorted Array is: 1 5 12 25 32 56 84 95 99 100 Heap Sort 堆排序 Original Array Elements : 2 5 -4 11 0 18 22 67 51 6 Sorted Array Elements : -4 0 2 5 6 11 18 22 51 67 Sorted Array Elements : -1 0.5 2.22 2.7 11.2 Sorted Array Elements : 江志文 刘慧 涂聚文 Black geovindu Orange Red White Radix Sort 基数排序 Original array : 2 5 -4 11 0 18 22 67 51 6 Sorted array : -4 0 2 5 6 11 18 22 51 67 Count Sort 计数排序 Sorted character array is I d e e g i l n o o u v v
from:
https://www.geeksforgeeks.org/counting-sort/
https://github.com/DragonSpit/HPCsharp
https://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
https://codereview.stackexchange.com/questions/68679/shell-sort-seems-inefficient
https://www.codeproject.com/articles/132757/visualization-and-comparison-of-sorting-algorithms
https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-5.php
https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-1.php