算法——排序算法

冒泡排序

• 时间复杂度：O(n2)
• 空间复杂度：O(1)
• 稳定排序

        public static void BubbleSort(int[] a)
        {
            for (int i = 0; i < a.Length; i++)
            {
                bool isFlag = false;
                for (int j = 0; j < a.Length - i - 1; j++)
                {
                    if (a[j] > a[j + 1])
                    {
                        isFlag = true;
                        //i与i+1比较
                        int temp = a[j + 1];
                        a[j + 1] = a[j];
                        a[j] = temp;
                    }
                }
                if (!isFlag) break;
            }
        }
这里定义了一个isFlag，是对冒泡排序的优化

选择排序

• 时间复杂度：O(n2)
• 空间复杂度：O(1)
• 非稳定排序

        public static void SelectSortFun(int[] a)
        {
            for (int i = 0; i < a.Length - 1; i++)
            {
                int min = i;
                for (int j = i + 1; j < a.Length; j++)
                {
                    if (a[min] > a[j])
                    {
                        //最小元素交换第i个元素
                        min = j;
                    }
                }
                int temp = a[min];
                a[min] = a[i];
                a[i] = temp;
            }
        }

插入排序

• 时间复杂度：O(n2)
• 空间复杂度：O(1)
• 稳定排序

        public static void InsertSort(int[] a)
        {
            for (int i = 1; i < a.Length; i++)
            {
                int inserted = a[i];
                int j = i - 1;
                for (; j >= 0 && a[j] > inserted; j--)
                {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = inserted;
            }
        }

希尔排序

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)
• 非稳定排序

        public static void SheelSort(int[] a)
        {
            for (int gap = a.Length / 2; gap > 0; gap /= 2)
            {
                for (int i = gap; i < a.Length; i++)
                {
                    int inserted = a[i];
                    int j;
                    for (j = i - gap; j >= 0 && a[j] > inserted; j -= gap)
                    {
                        a[j + gap] = a[j];
                    }
                    a[j + gap] = inserted;
                }
            }
        }

归并排序

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)
• 稳定排序

        public static void MergeSort(int[] a, int left, int right)
        {
            if (left < right)
            {
                int mid = (left + right) / 2;
                MergeSort(a, left, mid);
                MergeSort(a, mid + 1, right);
                Merge(a, left, mid, right);
            }
        }
        public static void MergeSort2(int[] a)
        {
            for (int i = 1; i < a.Length; i += i) 
            {
                int left = 0;
                int mid = left + i - 1;
                int right = mid + 1;
                while (right < a.Length) 
                {
                    Merge(a, left, mid, right);
                    left = right + 1;
                    mid = left + i - 1;
                    right = mid + i;
                }
                if (left < a.Length && mid < a.Length) 
                {
                    Merge(a, left, mid, a.Length - 1);
                }
            }
        }
        public static void Merge(int[] a, int left, int mid, int right)
        {
            int i = left, j = mid + 1;
            int[] temp = new int[right + j];
            for (int k = left; k <= right; k++)
            {
                if (i > mid)
                {
                    temp[k] = a[j++];
                }
                else if (j > right)
                {
                    temp[k] = a[i++];
                }
                else if (a[i] < a[j])
                {
                    temp[k] = a[i++];
                }
                else
                {
                    temp[k] = a[j++];
                }
            }
            for (int m = left; m <= right; m++)
            {
                a[m] = temp[m];
            }
        }