欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

常用排序算法c#

程序员文章站 2023-03-08 14:06:05
排序模版: 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 };...

排序模版:

 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