常用排序算法c#

排序模版：

 public static bool less(int a,int b)
    {
        return a - b < 0;
    }
    public static void exch(int[] a,int i,int j)
    {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

（1）冒泡排序
int[] arr = { 2, 3, 4, 67, 23, 99, 1 };

冒泡排序 n^2
  for (int j = 0; j <= arr.Length - 1; j++)
            {
                for (int i = 0; i < arr.Length - 1 - j; i++)
                {
                    if (arr[i] > arr[i + 1])
                    {
                        int temp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = temp;
                    }

                }
            } 

（2）插入排序

插入排序，希尔排序是其的改良版 n^2
public int[] Insertion(int[] a)
    {
        int length = a.Length;
        for(int i = 1; i < length; i++)
        {
            for(int j = i; j > 0 && less(a[j], a[j - 1]); j--)
            {
                exch(a, j, j - 1);
            }
        }
        return a;
    }

（3）选择排序

选择排序 n^2
public int[] Selection(int[] a)
    {
        int length = a.Length;
        for(int i = 0; i < length; i++)
        {
            int min = i;
            for(int j = i+1; j<a.Length;j++)
            {
                if (less(a[j], a[min]))
                    min = j;
            }
            exch(a, i, min);
        }
        return a;
    }

（4）希尔排序

   希尔排序 nlog2n
public int[] shell(int[] a)
	{
		int length = a.Length;
		int h = 1;
		while (h<length/3) h = 3 * h + 1;//分好间隔
		while (h >= 1)//一直逆推，让间隔=1
		{
			for (int i = h; i < length; i++)
			{

				for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
				{
					exch(a, j, j - h);
				}

			}
			h = h / 3;
		}
		
		return a;
	}

（5）快速排序

快速排序：空间1，时间nlogn
private static void QuickSort(int[] arr,int begin,int end){
	if(begin>=end) return;
	int pivotIndex=QuickSort_Once(arr,begin,end);
	QuickSort(arr,begin,pivotIndex-1);
	QuickSort(arr,pivotIndex+1,end);
}


private static int QuickSort_Once(int[] arr,int begin,int end){
	int pivot=arr[begin];
	int i=begin;
	int j=end;
	while(i<j){
		while(arr[j]>=pivot&&i<j)
		j--;
		arr[i]=arr[j];
		while(arr[i]<=pivot&&i<j)
		i++;
		arr[j]=arr[i];
	}
		arr[i]=pivot;
		return i;
	}
}

本文地址：https://blog.csdn.net/qq_42385019/article/details/107317055