常见排序算法

发表于 | 分类于

冒泡排序

算法：重复经过未排序数组，每次比较两个相邻元素，如果它们值相反，就交换它们的值
冒泡排序

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
static void BubbleSort(int[] a, int n)
	{
		for(int i=1; i<n; i++)
			for(int j=0; j<n-i;j++)
				if(a[j]>a[j+1])
				{
					int tmp;
					tmp = a[j];
					a[j] = a[j+1];
					a[j+1] = tmp;
				}
	}

插入排序

算法：每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕
插入排序
代码实现：

1
2
3
4
5
6
7
8
9
10
11
static void InsertSort(int[] a, int n)
	{
		for(int i=0; i<n; i++)
		{
			int m = a[i];
			int j;
			for(j=i; j>0&&m<a[j-1]; j--)
				a[j] = a[j-1];
			a[j] = m;
		}				           
	}

选择排序

算法：每一趟排序从序列中未排好序的那些元素中选择一个值最小的元素，然后将其与这些未排好序的元素的第一个元素交换位置
选择排序
代码实现：

static void SelectSort(int[] a, int n)
    {
        for(int i=0; i<n; i++)
        {
            int min = a[i];
            int index = i;
            int tmp;
            for(int j=i+1; j<n; j++)
                if(a[j]<min)
                {
                    min = a[j];
                    index = j;
                }
            tmp = a[i];
            a[i] = min;
            a[index] = tmp;
        }                                   
    }

快速排序

算法：先从数列中取出一个数作为基准数，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边，再对左右区间重复上述过程，直到各区间只有一个数
快速排序
代码实现：

static void QuickSort(int[] a, int left, int right)
    {
        if(left<right)
        {
            int i = left;
            int j = right;
            int m = a[i];
            while(i<j)
            {
                while(i<j&&a[j]>=m)
                    j--;
                if(i<j)
                    a[i++] = a[j];
                while(i<j&&a[i]<=m)
                    i++;
                if(i<j)
                    a[j--] = a[i];
            }
            a[i] = m;
            QuickSort(a, left, i-1);
            QuickSort(a, i+1, right);
        }
    }

最后

最后