首页 > 代码库 > 几种简单的排序

几种简单的排序

2024-09-20 23:22:39   220人阅读

1、简单选择排序

选择排序又叫简单选择排序。基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好的数列的最后。直到全部待排序数据元素排完。

        void select(int[] list)
        {
            int min = 0;
            for (int i = 0; i < list.Length; i++)
            {
                min = i;
                for (int j = i + 1; j < list.Length; j++)
                {
                    if (list[j] < list[min])
                    {
                        min = j;
                    }
                }
                if (i != min)
                    swap(list, i, min);
            }
        }

        void swap(int a,int b)
        {
            int itemp = a;
            a = b;
            b = itemp;
        }

 

2、直接插入排序

基本思想：顺序地将待排序的记录按关键码的大小插入到已排序的记录子序列的适当位置。子序列的记录个数从1开始逐渐增大，当子序列的记录个数与顺序表中的记录个数相同时排序完毕。

        void InsertSort(List<int> list)
        {
            for (int i = 1; i < list.Count; i++)
            {
                if (list[i] < list[i - 1])
                {
                    int temp = list[i];
                    int j = 0;
                    for (j = i - 1; j >= 0 && temp < list[j]; j--)
                    {
                        list[j + 1] = list[j];
                    }
                    list[j + 1] = temp;
                }
            }

        }

 

3、冒泡排序

首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则交换位置，然后比较第二个和第三个记录的关键字，依此类推，直到第n-1个记录和第n个记录比较过为止。此称为第一趟冒泡排序，结果是关键字最大的记录被交换到第n个记录的位置上。然后进行第二趟，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n-1个记录的位置。最多进行n-1趟，所有记录有序排列。若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。

        void mp(int[] list)
        {
            for (int i = 0; i < list.Length; i++)
            {
                for (int j = 0; j < list.Length - i - 1; j++)
                {
                    if (list[j] > list[j + 1])
                    {
                        int temp = list[j];
                        list[j] = list[j + 1];
                        list[j + 1] = temp;
                    }
                }
            }
        }

 

4、快速排序

任意取一个数作为枢纽元素，遍历整个数组，low位索引从前往后，high位索引从后往前，直到low位找到比枢纽大的位置，high找到比枢纽小的位置，交换这两个数据，然后low为索引继续往后，high位索引继续往前遍历。第一趟遍历完后，如果当前high位比低位大，再把低位到当前high位的数据进行上面的遍历交换，如果当前low位比最高位小，再把当前low位到最高位进行前面的遍历交换。最后整个数列就是有序排列了。

        void QuickSort(int[] pDataNum, int low, int high)
        {
            int i, j, iTemp, middle;
            i = low;
            j = high;
            middle = (low + high) / 2;//也可以是其他任意数据，low、high均可。我这里取的中位。

            while (i < j)
            {
                while ((pDataNum[i].CompareTo(pDataNum[middle]) < 0) && i < high)
                {
                    i++;
                }
                while (pDataNum[j].CompareTo(pDataNum[middle]) > 0 && j > low)
                {
                    j--;
                }
                if (i <= j)
                {
                    if (pDataNum[i] > pDataNum[j])
                    {
                        iTemp = pDataNum[i];
                        pDataNum[i] = pDataNum[j];
                        pDataNum[j] = iTemp;
                    }
                    i++;
                    j--;
                }
            }
            if (j > low)
                QuickSort(pDataNum, low, j);
            if (i < high)
                QuickSort(pDataNum, i, high);
        }

 

5、堆排序

直接排序中，顺序表是一个线性结构。要从有n个记录的顺序表中选择出一个最小的记录需要比较n-1次。如把待排序的n个记录构成一个完全二叉树结构，则每次选择出一个最大（或最小）的记录比较次数是完全二叉树的高度即log2n 次。则排序算法的时间复杂度就是 o(log2n)。

       /// <summary>
        /// 维护最大堆
        /// </summary>
        /// <param name="a"></param>
        /// <param name="i"></param>
        /// <param name="length"></param>
        void maxHeapify(int[] a,int i,int length)
        {
            int l = left(i);
            int r = right(i);
            int max;
            if(l<length&&a[l]>a[i])
            {
                max = l;
            }
            else
            {
                max = i;
            }
            if(r<length&&a[r]>a[max])
            {
                max = r;
            }
            if(max!=i)
            {
                swap(a, i, max);
                maxHeapify(a, max, length);
            }
        }

        int left(int i)
        {
            return 2 * i ;
        }

        int right(int i)
        {
            return 2 * i + 1;
        }


        /// <summary>
        /// 建堆
        /// </summary>
        /// <param name="a"></param>
        void buildMaxHeap(int[] a)
        {
            for (int i = a.Length/2+1; i >=0; i--)
            {
                maxHeapify(a, i,a.Length);
            }
        }


        void heapSort(int[] a)
        {
            //首先建立最大堆，完成后第一个元素为最大值。
            buildMaxHeap(a);
            int length = a.Length;
            for (int i = a.Length - 1; i >= 1; i--)
            {
                //将第一个最大的元素移到后面，并且在maxHeapify的过程中通过减小length忽略它。
                swap(a, i, 0);
                length--;
                maxHeapify(a, 0, length);
            }
        }

 

几种简单的排序


联系
我们