数据结构——排序

目录

1、冒泡排序

2、选择排序

3、插入排序

4、希尔排序

5、归并排序

6、快速排序

7、计数排序

8、桶排序

9、基数排序

正文

1、冒泡排序

• 冒泡排序是一种最简单的排序算法，其基本思想是迭代地对输入序列中的第一个元素到最后一个元素进行两两比较，当需要时交换这两个元素的位置。该过程持续迭代直到在一趟排序过程中不执行交换操作为止。
• 代码实现：

        public void BubbleSort(int[] A,int n) {
            for(int pass = n - 1; pass >= 0; pass--) {
                for (int i = 0; i < pass - 1; i++) {
                    if (A[i] > A[i + 1]) {
                        int temp = A[i];
                        A[i] = A[i + 1];
                        A[i + 1] = temp;
                    }
                }
            }
        }

• 上述算法的时间复杂度为 O（n^2）。可以通过增加一个标记来改进算法，在排序过程中，如果没有交换操作意味着排序完成。
• 代码实现：

        public void BubbleSortImproved(int[] A, int n) {
            int pass, i, temp, swapped = 1;
            for (pass = n - 1; pass >= 0 && swapped == 1; pass--) {
                swapped = 0;
                for (i = 0; i < pass - 1; i++) {
                    if (A[i] > A[i + 1]) {
                        temp = A[i];
                        A[i] = A[i + 1];
                        A[i + 1] = temp;
                        swapped = 1;
                    }
                }
            }
        }

• 性能：
  图1-1 冒泡排序性能

2、选择排序

• 算法过程：
  1）寻找序列中的最小值。
  2）用当前位置的值交换最小值。
  3）对所有元素重复上述过程，直至整个序列排序完成。
• 代码实现：

        public void SelectionSort(int[] A,int n) {
            int i, j, min, temp;
            for (i = 0; i < n - 1; i++) {
                min = i;
                for (j = i + 1; j < n; j++) {
                    if (A[j] < A[i]) {
                        min = j;
                    }
                }
                temp = A[min];
                A[min] = A[i];
                A[i] = temp;
            }
        }

• 性能：
  图2-1 选择排序性能

3、插入排序

• 算法过程：重复如下过程，每次从输入数据中移除一个元素，并将其插入已排序序列的正确位置，直到所有元素都插入有序序列。如图3-1所示，每个与x比较且大于x的元素复制到x的右边。
  

  图3-1 算法示意图

• 代码实现：

        public void InsertionSort(int[] A,int n) {
            int i, j, v;
            for (i = 0; i <=n - 1; i++) {
                v = A[i];
                j = i;
                while (j >= 1 && A[j - 1] > v ) {
                    A[j] = A[j - 1];
                    j--;
                }
                A[j] = v;
            }
        }

• 性能：
  图3-2 插入排序性能

4、希尔排序

• 算法过程： 希尔排序是对插入排序的一种扩展，两者的主要差异在于希尔排序具有交换相距较远元素的能力，这使得它能较快地把元素交换到所需位置。其主要思想是比较和交换数组中每个距离为h的元素，一旦以某个特定的h完成排序，则称数组是以h间距排序的数组。接下来的步骤就是以某一确定的序列依次减少间距h的值，并重新开始新一轮以h为间距的排序。一旦h变为1且是h间距排序的，则数组排序完成。
• 代码实现：

        public void ShellSort(int[] A,int n) {
            for(int i = n / 2; i > 0; i /= 2) {
                for(int j = i; j < n; j++) {
                    int v = j;
                    int temp = A[v];
                    if (A[v] < A[v - i]) {
                        while (v - i >= 0 && temp < A[v - i]) {
                            A[v] = A[v - i];
                            v -= i;
                        }
                        A[v] = temp;
                    }
                }
            }
        }

• 性能：
  图4-1 希尔排序性能

5、归并排序

• 算法过程：归并是把两个已排序文件合并成一个更大的已排序文件的过程。
• 代码实现：

        public void MergeSort(int[] A,int[] temp,int left,int right) {
            int mid;
            if (right > left) {
                mid = (right + left) / 2;
                MergeSort(A, temp, left, mid);
                MergeSort(A, temp, mid + 1, right);
                Merge(A,temp,left,mid+1,right);
            }
        }

        public void Merge(int[] A,int[] temp,int left,int mid,int right) {
            int i, left_end, size, temp_pos;
            left_end = mid - 1;
            temp_pos = left;
            size = right - left + 1;
            while ((left <= left_end) && (mid <= right)) {
                if (A[left] <= A[mid]) {
                    temp[temp_pos] = A[left];
                    temp_pos = temp_pos + 1;
                    left = left + 1;
                }
                else {
                    temp[temp_pos] = A[mid];
                    temp_pos = temp_pos + 1;
                    mid = mid + 1;
                }
            }
            while (left <= left_end) {
                temp[temp_pos] = A[left];
                left = left + 1;
                temp_pos = temp_pos + 1;    
            }
            while (mid <= right) {
                temp[temp_pos] = A[mid];
                mid = mid + 1;
                temp_pos = temp_pos + 1;
            }
            for(i = 0; i <= size; i++) {
                A[right] = temp[right];
                right = right - 1;
            }
        }

• 性能：
  图5-1 归并排序性能

6、快速排序

• 快速排序是分治算法技术的一个实例，快速排序采用递归调用对元素进行排序。
  1）划分：数组A[low...high]被分为两个子数组A[low...q]和A[q+1...high]，使得A[low...q]中的每一个元素都小于或等于A[q+1...high]中的元素。
  2）分而治之：对两个子数组A[low...q]和A[q+1...high]递归调用快速排序。
• 算法过程：
  1)、如果数组中仅有一个元素或者没有元素需要排序，则返回。
  2)、选择数组中的一个元素作为枢轴点（通常选择数组中最左的元素）。
  3)、把数组分为两部分——一部分元素大于枢轴，而另一部分元素小于枢轴。
  4)、对两数组分别递归调用该算法。
• 代码实现：

        public void QuickSort(int[] A,int low,int high) {
            int pivot;
            if (high > low) {
                pivot = Partition(A, low, high);
                QuickSort(A,low,pivot-1);
                QuickSort(A, pivot + 1, high);
            }
        }

        public int Partition(int[] A,int low,int high) {
            int left, right, pivot_item = A[low];
            left = low;
            right = high;
            while (left < right) {
                //当item<pivot移动左指针
                while (A[left] <= pivot_item) {
                    left++;
                }
                //当item>pivot移动左右指针
                while (A[right] > pivot_item) {
                    right--;
                }
                if (left < right) {
                    //交换左右元素
                    swap(A, left, right);
                }
            }
            //right 即是枢轴的最终位置
            A[low] = A[right];
            A[right] = pivot_item;
            return right;
        }

• 性能：
  图6-1 快速排序性能

7、计数排序

• 算法过程：计数排序假定每个输入元素都是1~K之间的整数，对于每一个输入元素X，确定小于X的元素个数，根据信息就可以将X直接放到正确的位置上。
• 代码实现：如下所示的代码中，A[0...n-1]是长度为n的输入数组，还需要额外的两个数组，假定数组B[0...n-1]用于存放排序结果，数组C[0...k-1]提供临时存储空间。

        public void CountingSort(int[] A,int n,int[] B,int k) {
            int[] C = new int[k];
            int i, j;
            for (i = 0; i < k; i++) {
                C[i] = 0;
            }
            for (j = 0; j < n; j++) {
                C[A[j]] = C[A[j]] + 1;
            }
            for (i = 1; i < k; i++) {
                C[i] = C[i] + C[i - 1];
            }
            for (j = n - 1; j >= 0; j--) {
                B[C[A[j]]] = A[j];
                C[A[j]] = C[A[j]] - 1;
            }
        }

8、桶排序

• 算法过程： 桶排序也对输入做了限制，假设所有输入元素来自{0，1，...，K-1}，即在区间[0，K-1]上的整数集合，那么桶排序采用K个计数器，第i个计数器记录第i个元素的出现次数。

• 代码实现：

        public void BucketSort(int[] A,int array_size) {
            int i, j, k;
            int[] buckets=new int[BUCKETS];
            for (j = 0; j < BUCKETS; j++) {
                buckets[j] = 0;
            }
            for (i = 0; i < array_size; i++) {
                ++buckets[A[i]];
            }
            for (i = 0, j = 0; j < BUCKETS; j++) {
                for (k = buckets[j]; k > 0; k--) {
                    A[i++] = j;
                }
            }
        }

9、基数排序

• 算法过程：基数排序也对输入元素做某种假设，假定待排序的输入值是以d为基数，即所有数值均为d数位数。首先基于最后一位数字（最低有效位）排序，随后该结果又以第二位（最低有效位的相邻位排序），重复该过程直至算法达到最高位。