排序算法(一)---插入与归并2017-11-10 03:43:06

插入排序

    对于少量元素,插入排序是一个有效的算法。插入排序就像是排序手中的扑克牌,每次我们从牌堆里抽出一张牌,并将它与手中的牌逐个比较,然后把它放入正确的位置。

    该算法原址排序,即算法在原数组中重排这些数,在任何时候,最多只有其中的常数个数字存储在数组外面。在算法结束后,该数组里的元素已经以某种顺序排好了。

代码如下:

using namespace std;
int main()
{
       int array[7] = { 6,3,5,2,9,8,4 };
       int length = sizeof(array) / sizeof(int);
       int key,i;
       for (int j = 1; j < length; j++) {
              key = array[j];
              i = j - 1;
              while (i >= 0 && array[i] > key) {
                     array[i + 1] = array[i];
                     i = i - 1;
              }
              array[i + 1] = key;
       }
       for (int iter = 0; iter < length; iter++) {
              cout << array[iter] << endl;
       }
    return 0;
}


如何理解:

该算法就像是在玩扑克,当你在斗地主时,你拿到一手的牌,自然需要对它排序,从你的手的第二张牌开始,需要依次对前面的牌进行排序,上述代码是将数组里的数从小到大进行排序。你手中拿的需要排序的牌为key,它在原数组中的序号是j。初始的ij的前一张牌。Key只需要与序号为i的牌进行比较,如果key大于它则key所在的位置是正确的,无需调整,而i之前的牌已经排序,此时这张牌已经完成排序。如果key小于它,那么说明key至少应排在i之前,这时候序号为i的元素,它的序号应该加一,key要跟i之前的序号再进行一次比较,如果key大于它的话,那么key的位置也就确定了,即是i。如果key小于它的话,那么就对数组的元素再进行一次调序,具体流程与上述相同。直到算法结束,数组的元素就全部有序了。

 

归并排序

分治法

许多算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归的调用其自身以解决紧密相关的若干的子问题。分治法的思想就是将原问题分解为几个规模较小的但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。

   分治模式在每层递归时有三个步骤:1、分解 2、解决 3、合并。

归并排序也是遵从这三个步骤:

1、 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。

2、 解决 :使用归并排序递归的排序两个子序列

3、 合并:合并两个已经排序的子序列。

该算法的最关键步骤就是合并操作。

代码如下:

void merge(int* array, int p, int q, int r) {   //array 为原数组, p,q,r为数组下标 被合成的数组为下标为p至q,和q+1至r.
       int n1 = q - p + 1;
       int n2 = r - q;
       int i, j;
       int L[50], R[50];
       for (i = 0; i < n1; i++) {
              L[i] = *(array + (p + i));
       }
       for (j = 0; j < n2; j++) {
              R[j] = *(array + (q + 1 + j));
       }
       L[n1] = 1000;  //此处应该是标志位,表示无穷大
       R[n2] = 1000;  //此处应该是标志位,表示无穷大
       i = 0;
       j = 0;
       for (int k = p; k <= r; k++) {
              if (L[i] <= R[j]) {
                     *(array + k) = L[i];
                     i++;
              }
              else {
                     *(array + k) = R[j];
                     j++;
              }
       }
}


如何理解:

    这里可以理解为已经经过排序的两堆牌,然后依次在每堆牌上取第一张,比较大小,将较小的一张拿出,然后继续执行这个操作,直到有一堆牌已经被取光,此时剩下的那堆牌就是比较大的,直接依次放置即可,这样就将两堆牌合并。并且是有序的。

利用上述算法对数组的排序代码如下:

void merge_sort(int* array, int p, int r) {
       int q;
       if (p < r) {
              q = (p + r) / 2;
              merge_sort(array, p, q);
              merge_sort(array, q + 1, r);
              merge(array, p, q, r);
       }
}

sort1.png


linweiyu

Something should be here;

0 Thoughts

Leave a Thought