白话经典算法系列

时间：2021-07-05 09:48:41

白话经典算法系列之一 冒泡排序的三种实现

冒泡排序是非常容易理解和实现，，以从小到大排序举例：

设数组长度为N。

1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。

2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。

3．N=N-1，如果N不为0就重复前面二步，否则排序完成。

 

按照定义很容易写出代码：

[cpp] view plaincopy
  1. //冒泡排序1  
  2. void BubbleSort1(int a[], int n)  
  3. {  
  4.        int i, j;  
  5.        for (i = 0; i < n; i++)  
  6.               for (j = 1; j < n - i; j++)  
  7.                      if (a[j - 1] > a[j])  
  8.                             Swap(a[j - 1], a[j]);  
  9. }  


下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。

[cpp] view plaincopy
  1.   
 [cpp] view plaincopy
  1. //冒泡排序2  
  2. void BubbleSort2(int a[], int n)  
  3. {  
  4.        int j, k;  
  5.        bool flag;  
  6.   
  7.        k = n;  
  8.        flag = true;  
  9.        while (flag)  
  10.        {  
  11.               flag = false;  
  12.               for (j = 1; j < k; j++)  
  13.                      if (a[j - 1] > a[j])  
  14.                      {  
  15.                             Swap(a[j - 1], a[j]);  
  16.                             flag = true;  
  17.                      }  
  18.               k--;  
  19.        }  
  20. }  

再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。

[cpp] view plaincopy
  1. //冒泡排序3  
  2. void BubbleSort3(int a[], int n)  
  3. {  
  4.     int j, k;  
  5.     int flag;  
  6.       
  7.     flag = n;  
  8.     while (flag > 0)  
  9.     {  
  10.         k = flag;  
  11.         flag = 0;  
  12.         for (j = 1; j < k; j++)  
  13.             if (a[j - 1] > a[j])  
  14.             {  
  15.                 Swap(a[j - 1], a[j]);  
  16.                 flag = j;  
  17.             }  
  18.     }  
  19. }  

冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。


白话经典算法系列之二 直接插入排序的三种实现

直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

 

设数组为a[0…n-1]。

1.      初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1

2.      将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。

3.      i++并重复第二步直到i==n-1。排序完成。

 

下面给出严格按照定义书写的代码（由小到大排序）：

[cpp] view plaincopy
  1. void Insertsort1(int a[], int n)  
  2. {  
  3.     int i, j, k;  
  4.     for (i = 1; i < n; i++)  
  5.     {  
  6.         //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置  
  7.         for (j = i - 1; j >= 0; j--)  
  8.             if (a[j] < a[i])  
  9.                 break;  
  10.   
  11.         //如找到了一个合适的位置  
  12.         if (j != i - 1)  
  13.         {  
  14.             //将比a[i]大的数据向后移  
  15.             int temp = a[i];  
  16.             for (k = i - 1; k > j; k--)  
  17.                 a[k + 1] = a[k];  
  18.             //将a[i]放到正确位置上  
  19.             a[k + 1] = temp;  
  20.         }  
  21.     }  
  22. }  

这样的代码太长了，不够清晰。现在进行一下改写，将搜索和数据后移这二个步骤合并。即每次a[i]先和前面一个数据a[i-1]比较，如果a[i] > a[i-1]说明a[0…i]也是有序的，无须调整。否则就令j=i-1,temp=a[i]。然后一边将数据a[j]向后移动一边向前搜索，当有数据a[j]<a[i]时停止并将temp放到a[j + 1]处。

[cpp] view plaincopy
  1. void Insertsort2(int a[], int n)  
  2. {  
  3.     int i, j;  
  4.     for (i = 1; i < n; i++)  
  5.         if (a[i] < a[i - 1])  
  6.         {  
  7.             int temp = a[i];  
  8.             for (j = i - 1; j >= 0 && a[j] > temp; j--)  
  9.                 a[j + 1] = a[j];  
  10.             a[j + 1] = temp;  
  11.         }  
  12. }  


再对将a[j]插入到前面a[0…j-1]的有序区间所用的方法进行改写，用数据交换代替数据后移。如果a[j]前一个数据a[j-1] > a[j]，就交换a[j]和a[j-1]，再j--直到a[j-1] <= a[j]。这样也可以实现将一个新数据新并入到有序区间。

[cpp] view plaincopy
  1. void Insertsort3(int a[], int n)  
  2. {  
  3.     int i, j;  
  4.     for (i = 1; i < n; i++)  
  5.         for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)  
  6.             Swap(a[j], a[j + 1]);  
  7. }  
 白话经典算法系列之三 希尔排序的实现

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

 

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

 

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

第一次 gap = 10 / 2 = 5

49   38   65   97   26   13   27   49   55   4

1A                                        1B

        2A                                         2B

                 3A                                         3B

                         4A                                          4B

                                  5A                                         5B

1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)这样每组排序后就变成了(13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26)，下同。

第二次 gap = 5 / 2 = 2

排序后

13   27   49   55   4    49   38   65   97   26

1A             1B             1C              1D            1E

        2A               2B             2C             2D              2E

第三次 gap = 2 / 2 = 1

4   26   13   27   38    49   49   55   97   65

1A   1B     1C    1D    1E      1F     1G    1H     1I     1J

第四次 gap = 1 / 2 = 0 排序完成得到数组：

4   13   26   27   38    49   49   55   65   97

 

下面给出严格按照定义来写的希尔排序

[cpp] view plaincopy
  1. void shellsort1(int a[], int n)  
  2. {  
  3.     int i, j, gap;  
  4.   
  5.     for (gap = n / 2; gap > 0; gap /= 2) //步长  
  6.         for (i = 0; i < gap; i++)        //直接插入排序  
  7.         {  
  8.             for (j = i + gap; j < n; j += gap)   
  9.                 if (a[j] < a[j - gap])  
  10.                 {  
  11.                     int temp = a[j];  
  12.                     int k = j - gap;  
  13.                     while (k >= 0 && a[k] > temp)  
  14.                     {  
  15.                         a[k + gap] = a[k];  
  16.                         k -= gap;  
  17.                     }  
  18.                     a[k + gap] = temp;  
  19.                 }  
  20.         }  
  21. }  

很明显，上面的shellsort1代码虽然对直观的理解希尔排序有帮助，但代码量太大了，不够简洁清晰。因此进行下改进和优化，以第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比较，然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。这种每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。

[cpp] view plaincopy
  1. void shellsort2(int a[], int n)  
  2. {  
  3.     int j, gap;  
  4.       
  5.     for (gap = n / 2; gap > 0; gap /= 2)  
  6.         for (j = gap; j < n; j++)//从数组第gap个元素开始  
  7.             if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序  
  8.             {  
  9.                 int temp = a[j];  
  10.                 int k = j - gap;  
  11.                 while (k >= 0 && a[k] > temp)  
  12.                 {  
  13.                     a[k + gap] = a[k];  
  14.                     k -= gap;  
  15.                 }  
  16.                 a[k + gap] = temp;  
  17.             }  
  18. }  


再将直接插入排序部分用 白话经典算法系列之二 直接插入排序的三种实现  中直接插入排序的第三种方法来改写下：

[cpp] view plaincopy
  1. void shellsort3(int a[], int n)  
  2. {  
  3.     int i, j, gap;  
  4.   
  5.     for (gap = n / 2; gap > 0; gap /= 2)  
  6.         for (i = gap; i < n; i++)  
  7.             for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)  
  8.                 Swap(a[j], a[j + gap]);  
  9. }  

这样代码就变得非常简洁了。

  

附注：上面希尔排序的步长选择都是从n/2开始，每次再减半，直到最后为1。其实也可以有另外的更高效的步长选择，如果读者有兴趣了解，请参阅*上对希尔排序步长的说明：

http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F


白话经典算法系列之四 直接选择排序及交换二个数据的正确实现

直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。

 

设数组为a[0…n-1]。

1.      初始时，数组全为无序区为a[0..n-1]。令i=0

2.      在无序区a[i…n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。

3.      i++并重复第二步直到i==n-1。排序完成。

 

直接选择排序无疑是最容易实现的，下面给出代码：

[cpp] view plaincopy
  1. void Selectsort(int a[], int n)  
  2. {  
  3.     int i, j, nMinIndex;  
  4.     for (i = 0; i < n; i++)  
  5.     {  
  6.         nMinIndex = i; //找最小元素的位置  
  7.         for (j = i + 1; j < n; j++)  
  8.             if (a[j] < a[nMinIndex])  
  9.                 nMinIndex = j;  
  10.   
  11.         Swap(a[i], a[nMinIndex]); //将这个元素放到无序区的开头  
  12.     }  
  13. }  

在这里，要特别提醒各位注意下Swap()的实现，建议用：

[cpp] view plaincopy
  1. inline void Swap(int &a, int &b)  
  2. {  
  3.     int c = a;  
  4.     a = b;  
  5.     b = c;  
  6. }  

笔试面试时考不用中间数据交换二个数，很多人给出了

[cpp] view plaincopy
  1. inline void Swap1(int &a, int &b)  
  2. {  
  3.     a ^= b;  
  4.     b ^= a;  
  5.     a ^= b;  
  6. }  

在网上搜索下，也可以找到许多这样的写法。不过这样写存在一个隐患，如果a, b指向的是同一个数，那么调用Swap1()函数会使这个数为0。如:

[cpp] view plaincopy
  1. int i = 6;  
  2. Swap2(i, i);  
  3. printf("%d %d\n", i);  

当然谁都不会在程序中这样的写代码，但回到我们的Selectsort()，如果a[0]就是最小的数，那么在交换时，将会出现将a[0]置0的情况，这种错误相信调试起来也很难发现吧，因此建议大家将交换二数的函数写成：

[cpp] view plaincopy
  1. inline void Swap(int &a, int &b)  
  2. {  
  3.     int c = a;  
  4.     a = b;  
  5.     b = c;  
  6. }  

或者在Swap1()中加个判断，如果二个数据相等就不用交换了：

[cpp] view plaincopy
  1. inline void Swap1(int &a, int &b)  
  2. {  
  3.     if (a != b)  
  4.     {  
  5.         a ^= b;  
  6.         b ^= a;  
  7.         a ^= b;  
  8.     }  
  9. }  

 白话经典算法系列之五 归并排序的实现

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

[cpp] view plaincopy
  1. //将有序数组a[]和b[]合并到c[]中  
  2. void MemeryArray(int a[], int n, int b[], int m, int c[])  
  3. {  
  4.     int i, j, k;  
  5.   
  6.     i = j = k = 0;  
  7.     while (i < n && j < m)  
  8.     {  
  9.         if (a[i] < b[j])  
  10.             c[k++] = a[i++];  
  11.         else  
  12.             c[k++] = b[j++];   
  13.     }  
  14.   
  15.     while (i < n)  
  16.         c[k++] = a[i++];  
  17.   
  18.     while (j < m)  
  19.         c[k++] = b[j++];  
  20. }  

可以看出合并有序数列的效率是比较高的，可以达到O(n)。

解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

[cpp] view plaincopy
  1. //将有二个有序数列a[first...mid]和a[mid...last]合并。  
  2. void mergearray(int a[], int first, int mid, int last, int temp[])  
  3. {  
  4.     int i = first, j = mid + 1;  
  5.     int m = mid,   n = last;  
  6.     int k = 0;  
  7.       
  8.     while (i <= m && j <= n)  
  9.     {  
  10.         if (a[i] <= a[j])  
  11.             temp[k++] = a[i++];  
  12.         else  
  13.             temp[k++] = a[j++];  
  14.     }  
  15.       
  16.     while (i <= m)  
  17.         temp[k++] = a[i++];  
  18.       
  19.     while (j <= n)  
  20.         temp[k++] = a[j++];  
  21.       
  22.     for (i = 0; i < k; i++)  
  23.         a[first + i] = temp[i];  
  24. }  
  25. void mergesort(int a[], int first, int last, int temp[])  
  26. {  
  27.     if (first < last)  
  28.     {  
  29.         int mid = (first + last) / 2;  
  30.         mergesort(a, first, mid, temp);    //左边有序  
  31.         mergesort(a, mid + 1, last, temp); //右边有序  
  32.         mergearray(a, first, mid, last, temp); //再将二个有序数列合并  
  33.     }  
  34. }  
  35.   
  36. bool MergeSort(int a[], int n)  
  37. {  
  38.     int *p = new int[n];  
  39.     if (p == NULL)  
  40.         return false;  
  41.     mergesort(a, 0, n - 1, p);  
  42.     delete[] p;  
  43.     return true;  
  44. }  

 

归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

 

在本人电脑上对冒泡排序，直接插入排序，归并排序及直接使用系统的qsort()进行比较（均在Release版本下）

对20000个随机数据进行测试：

白话经典算法系列

对50000个随机数据进行测试：

白话经典算法系列

再对200000个随机数据进行测试：

白话经典算法系列

 

注：有的书上是在mergearray()合并有序数列时分配临时数组，但是过多的new操作会非常费时。因此作了下小小的变化。只在MergeSort()中new一个临时数组。后面的操作都共用这一个临时数组。

 

白话经典算法系列之六 快速排序 快速搞定

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。

总的说来，要直接默写出快速排序还是有一定难度的，因为本人就自己的理解对快速排序作了下白话解释，希望对大家理解有帮助，达到快速排序，快速搞定。

 

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

 

虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法：

先来看实例吧，定义下面再给出（最好能用自己的话来总结定义，这样对实现代码会有帮助）。

 

以一个数组作为示例，取区间第一个数为基准数。

0

1

2

3

4

5

6

7

8

9

72

6

57

88

60

42

83

73

48

85

初始时，i = 0;  j = 9;   X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

 

数组变为：

0

1

2

3

4

5

6

7

8

9

48

6

57

88

60

42

83

73

88

85

 i = 3;   j = 7;   X=72

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

 

数组变为：

0

1

2

3

4

5

6

7

8

9

48

6

57

42

60

72

83

73

88

85

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

 

 

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

照着这个总结很容易实现挖坑填数的代码：

[cpp] view plaincopy
  1. int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置  
  2. {  
  3.     int i = l, j = r;  
  4.     int x = s[l]; //s[l]即s[i]就是第一个坑  
  5.     while (i < j)  
  6.     {  
  7.         // 从右向左找小于x的数来填s[i]  
  8.         while(i < j && s[j] >= x)   
  9.             j--;    
  10.         if(i < j)   
  11.         {  
  12.             s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑  
  13.             i++;  
  14.         }  
  15.   
  16.         // 从左向右找大于或等于x的数来填s[j]  
  17.         while(i < j && s[i] < x)  
  18.             i++;    
  19.         if(i < j)   
  20.         {  
  21.             s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑  
  22.             j--;  
  23.         }  
  24.     }  
  25.     //退出时，i等于j。将x填到这个坑中。  
  26.     s[i] = x;  
  27.   
  28.     return i;  
  29. }  

再写分治法的代码：

[cpp] view plaincopy
  1. void quick_sort1(int s[], int l, int r)  
  2. {  
  3.     if (l < r)  
  4.     {  
  5.         int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]  
  6.         quick_sort1(s, l, i - 1); // 递归调用   
  7.         quick_sort1(s, i + 1, r);  
  8.     }  
  9. }  

这样的代码显然不够简洁，对其组合整理下：

[cpp] view plaincopy
  1. //快速排序  
  2. void quick_sort(int s[], int l, int r)  
  3. {  
  4.     if (l < r)  
  5.     {  
  6.         //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1  
  7.         int i = l, j = r, x = s[l];  
  8.         while (i < j)  
  9.         {  
  10.             while(i < j && s[j] >= x) // 从右向左找第一个小于x的数  
  11.                 j--;    
  12.             if(i < j)   
  13.                 s[i++] = s[j];  
  14.               
  15.             while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数  
  16.                 i++;    
  17.             if(i < j)   
  18.                 s[j--] = s[i];  
  19.         }  
  20.         s[i] = x;  
  21.         quick_sort(s, l, i - 1); // 递归调用   
  22.         quick_sort(s, i + 1, r);  
  23.     }  
  24. }  

快速排序还有很多改进版本，如随机选择基准数，区间内数据较少时直接用另的方法排序以减小递归深度。有兴趣的筒子可以再深入的研究下。

 

注1，有的书上是以中间的数作为基准数的，要实现这个方便非常方便，直接将中间的数和第一个数进行交换就可以了。

 

 转载请标明出处，原文地址：http://blog.csdn.net/morewindows/article/details/6684558


白话经典算法系列之七 堆与堆排序

堆排序与快速排序，归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前，先讲解下什么是数据结构中的二叉堆。

二叉堆的定义

二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足二个特性：

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：

白话经典算法系列

由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。

堆的存储

一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

白话经典算法系列

堆的操作——插入删除

下面先给出《数据结构C++语言描述》中最小堆的建立插入删除的图解，再给出本人的实现代码，最好是先看明白图后再去看代码。

白话经典算法系列

堆的插入

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中，对照《白话经典算法系列之二 直接插入排序的三种实现》不难写出插入一个新数据时堆的调整代码：

[cpp] view plaincopy
  1. //  新加入i结点  其父结点为(i - 1) / 2  
  2. void MinHeapFixup(int a[], int i)  
  3. {  
  4.     int j, temp;  
  5.       
  6.     temp = a[i];  
  7.     j = (i - 1) / 2;      //父结点  
  8.     while (j >= 0 && i != 0)  
  9.     {  
  10.         if (a[j] <= temp)  
  11.             break;  
  12.           
  13.         a[i] = a[j];     //把较大的子结点往下移动,替换它的子结点  
  14.         i = j;  
  15.         j = (i - 1) / 2;  
  16.     }  
  17.     a[i] = temp;  
  18. }  

更简短的表达为：

[cpp] view plaincopy
  1. void MinHeapFixup(int a[], int i)  
  2. {  
  3.     for (int j = (i - 1) / 2; (j >= 0 && i != 0)&& a[i] > a[j]; i = j, j = (i - 1) / 2)  
  4.         Swap(a[i], a[j]);  
  5. }  

插入时：

[cpp] view plaincopy
  1. //在最小堆中加入新的数据nNum  
  2. void MinHeapAddNumber(int a[], int n, int nNum)  
  3. {  
  4.     a[n] = nNum;  
  5.     MinHeapFixup(a, n);  
  6. }  

堆的删除

按定义，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。下面给出代码：

[cpp] view plaincopy
  1. //  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  
  2. void MinHeapFixdown(int a[], int i, int n)  
  3. {  
  4.     int j, temp;  
  5.   
  6.     temp = a[i];  
  7.     j = 2 * i + 1;  
  8.     while (j < n)  
  9.     {  
  10.         if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的  
  11.             j++;  
  12.   
  13.         if (a[j] >= temp)  
  14.             break;  
  15.   
  16.         a[i] = a[j];     //把较小的子结点往上移动,替换它的父结点  
  17.         i = j;  
  18.         j = 2 * i + 1;  
  19.     }  
  20.     a[i] = temp;  
  21. }  
  22. //在最小堆中删除数  
  23. void MinHeapDeleteNumber(int a[], int n)  
  24. {  
  25.     Swap(a[0], a[n - 1]);  
  26.     MinHeapFixdown(a, 0, n - 1);  
  27. }  

堆化数组

有了堆的插入和删除后，再考虑下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吧，不用！先看一个数组，如下图：

白话经典算法系列

很明显，对叶子结点来说，可以认为它已经是一个合法的堆了即20，60， 65， 4， 49都分别是一个合法的堆。只要从A[4]=50开始向下调整就可以了。然后再取A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9分别作一次向下调整操作就可以了。下图展示了这些步骤：

白话经典算法系列

写出堆化数组的代码：

[cpp] view plaincopy
  1. //建立最小堆  
  2. void MakeMinHeap(int a[], int n)  
  3. {  
  4.     for (int i = n / 2 - 1; i >= 0; i--)  
  5.         MinHeapFixdown(a, i, n);  
  6. }  


至此，堆的操作就全部完成了(注1)，再来看下如何用堆这种数据结构来进行排序。

堆排序

首先可以看到堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。

由于堆也是用数组模拟的，故堆化数组后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。有点类似于直接选择排序。

[cpp] view plaincopy
  1. void MinheapsortTodescendarray(int a[], int n)  
  2. {  
  3.     for (int i = n - 1; i >= 1; i--)  
  4.     {  
  5.         Swap(a[i], a[0]);  
  6.         MinHeapFixdown(a, 0, i);  
  7.     }  
  8. }  

注意使用最小堆排序后是递减数组，要得到递增数组，可以使用最大堆。

由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)。STL也实现了堆的相关函数，可以参阅《STL系列之四 heap 堆》。

 

 

注1 作为一个数据结构，最好用类将其数据和方法封装起来，这样即便于操作，也便于理解。此外，除了堆排序要使用堆，另外还有很多场合可以使用堆来方便和高效的处理数据，以后会一一介绍。

 

 

转载请标明出处，原文地址：http://blog.csdn.net/morewindows/article/details/6709644


白话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇

  在我的博客对冒泡排序，直接插入排序，直接选择排序，希尔排序，归并排序，快速排序和堆排序这七种常用的排序方法进行了详细的讲解，并做成了电子书以供大家下载。下载地址为：http://download.csdn.net/detail/morewindows/4443208。

       有网友提议到这本《MoreWindows白话经典算法之七大排序》电子书讲解细致用来平时学习是非常好的，但是页数有22页，不太合适做面试前的复习资料。因此在这里将这七种常用的排序方法进行下总结，以便大家更好的复习这些经典的排序算法，为面试打下良好的基础。

 

首先回顾下各种排序的主要思路：

一．       冒泡排序

冒泡排序主要思路是：

通过交换使相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了。重复N次即可以使数组有序。


冒泡排序改进1：在某次遍历中如果没有数据交换，说明整个数组已经有序。因此通过设置标志位来记录此次遍历有无数据交换就可以判断是否要继续循环。


冒泡排序改进2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。

 

二．       直接插入排序

直接插入排序主要思路是：

每次将一个待排序的数据，插入到前面已经排好序的序列之中，直到全部数据插入完成。

 

三．       直接选择排序

直接选择排序主要思路是：

数组分成有序区和无序区，初始时整个数组都是无序区，然后每次从无序区选一个最小的元素直接放到有序区的最后，直到整个数组变有序区。


上面这三种排序都是非常简单的，下面这四种排序略有难度，希望读者能多多实践以加深理解。

 

四．       希尔排序

希尔排序主要思路是：

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。由于希尔排序是对相隔若干距离的数据进行直接插入排序，因此可以形象的称希尔排序为“跳着插”

 

五．       归并排序

归并排序主要思路是：

当一个数组左边有序，右边也有序，那合并这两个有序数组就完成了排序。如何让左右两边有序了？用递归！这样递归下去，合并上来就是归并排序。

 

六．       快速排序

快速选择排序主要思路是：

“挖坑填数+分治法”，首先令i =L; j = R; 将a[i]挖出形成第一个坑，称a[i]为基准数。然后j--由后向前找比基准数小的数，找到后挖出此数填入前一个坑a[i]中，再i++由前向后找比基准数大的数，找到后也挖出此数填到前一个坑a[j]中。重复进行这种“挖坑填数”直到i==j。再将基准数填入a[i]中，这样i之前的数都比基准数小，i之后的数都比基准数大。因此将数组分成二部分再分别重复上述步骤就完成了排序。

 

七．       堆排序

堆排序主要思路用张图示来表示更好：

白话经典算法系列

可见堆排序的难点就在于堆的的插入和删除。

堆的插入就是——每次插入都是将新数据放在数组最后，而从这个新数据的父结点到根结点必定是一个有序的数列，因此只要将这个新数据插入到这个有序数列中即可。

堆的删除就是——堆的删除就是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点开始将一个数据在有序数列中进行“下沉”。

因此，堆的插入和删除非常类似直接插入排序，只不是在二叉树上进行插入过程。所以可以将堆排序形容为“树上插”

 

 

再用一张图表示下这七种常用的排序方法的关系。

 白话经典算法系列

 


好了，七种常用的排序方法就总结到这了，相信大家上机写下代码再看下这张图必定会印象深刻。在准备面试资料时可以打印最后这张图，这样就能在面试前快速的复习一下了，祝大家面试顺利，拿到自己满意的offer。

 

新版电子书《MoreWindows白话经典算法之七大排序第2版(高清)》已经上传成功，下载地址是：http://download.csdn.net/detail/morewindows/4560056

 

转载请标明出处，原文地址：http://blog.csdn.net/morewindows/article/details/7961256


白话经典算法系列之九 从归并排序到数列的逆序数对（微软笔试题）

首先来看看原题

 

微软2010年笔试题

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序数。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，因此整个数组的逆序数对个数为4，现在给定一数组，要求统计出该数组的逆序数对个数。

 

计算数列的逆序数对个数最简单的方便就最从前向后依次统计每个数字与它后面的数字是否能组成逆序数对。代码如下：

[cpp] view plaincopy
  1. #include <stdio.h>  
  2. int main()  
  3. {  
  4.     printf("     数列的逆序数对 \n");      
  5.     printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");      
  6.   
  7.     const int MAXN = 8;  
  8.     int a[MAXN] = {1, 7, 2, 9, 6, 4, 5, 3};  
  9.       
  10.     int nCount = 0;  
  11.     int i, j;  
  12.     for (i = 0; i < MAXN; i++)  
  13.         for (j = i + 1; j < MAXN; j++)  
  14.             if (a[i] > a[j])  
  15.                 nCount++;  
  16.   
  17.     printf("逆序数对为: %d\n", nCount);  
  18. }  

运行结果如下：

白话经典算法系列

这种方法用到了双循环，时间复杂度为O(N^2)，是一个不太优雅的方法。因此我们尝试用其它方法来解决。

 

在《白话经典算法系列之五归并排序的实现》中观察归并排序——合并数列(1，3，5)与(2，4)的时候：

1．先取出前面数列中的1。

2．然后取出后面数列中的2，明显！这个2和前面的3，5都可以组成逆序数对即3和2，5和2都是逆序数对。

3．然后取出前面数列中的3。

4．然后取出后面数列中的4，同理，可知这个4和前面数列中的5可以组成一个逆序数对。

这样就完成了逆序数对的统计，归并排序的时间复杂度是O(N * LogN)，因此这种从归并排序到数列的逆序数对的解法的时间复杂度同样是O(N * LogN)，下面给出代码：

[cpp] view plaincopy
  1. //从归并排序到数列的逆序数对  
  2. #include <stdio.h>  
  3. int g_nCount;  
  4. void mergearray(int a[], int first, int mid, int last, int temp[])  
  5. {  
  6.     int i = first, j = mid + 1;  
  7.     int m = mid,   n = last;  
  8.     int k = 0;  
  9.   
  10.     while (i <= m && j <= n) //a[i] 前面的数  a[j] 后面的数  
  11.     {  
  12.         if (a[i] < a[j])  
  13.             temp[k++] = a[i++];  
  14.         else  
  15.         {  
  16.             temp[k++] = a[j++];  
  17.             //a[j]和前面每一个数都能组成逆序数对  
  18.             g_nCount += m - i + 1;  
  19.         }  
  20.     }  
  21.   
  22.     while (i <= m)  
  23.         temp[k++] = a[i++];  
  24.   
  25.     while (j <= n)  
  26.         temp[k++] = a[j++];  
  27.   
  28.     for (i = 0; i < k; i++)  
  29.         a[first + i] = temp[i];  
  30. }  
  31. void mergesort(int a[], int first, int last, int temp[])  
  32. {  
  33.     if (first < last)  
  34.     {  
  35.         int mid = (first + last) / 2;  
  36.         mergesort(a, first, mid, temp);    //左边有序  
  37.         mergesort(a, mid + 1, last, temp); //右边有序  
  38.         mergearray(a, first, mid, last, temp); //再将二个有序数列合并  
  39.     }  
  40. }  
  41.   
  42. bool MergeSort(int a[], int n)  
  43. {  
  44.     int *p = new int[n];  
  45.     if (p == NULL)  
  46.         return false;  
  47.     mergesort(a, 0, n - 1, p);  
  48.     return true;  
  49. }  
  50.   
  51. int main()  
  52. {  
  53.     printf("     从归并排序到数列的逆序数对 \n");      
  54.     printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");      
  55.   
  56.     const int MAXN = 8;  
  57.     int a[MAXN] = {1, 7, 2, 9, 6, 4, 5, 3};  
  58.   
  59.     g_nCount = 0;  
  60.     MergeSort(a, MAXN);  
  61.     printf("逆序数对为: %d\n", g_nCount);  
  62.     return 0;  
  63. }  

运行结果：

白话经典算法系列

 

 

好了，介绍到这里后，相信大家对如何求数列的逆序数对已经有了很好的认识，文章中所用到的“知识迁移”这种方法还是不错的，值得大家掌握。

 

 

转载请标明出处，原文地址：http://blog.csdn.net/morewindows/article/details/8029996


白话经典算法系列之十 一道有趣的GOOGLE面试题

微博http://weibo.com/MoreWindows已开通，欢迎关注。

最近在微博上看到一道有趣的GOOGLE面试题，见下图：

白话经典算法系列

文字版：

一个大小为n的数组，里面的数都属于范围[0, n-1]，有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。

 

    这个题目要求用O(n)的时间复杂度，这意味着只能遍历数组一次。同时还要寻找重复元素，很容易想到建立哈希表来完成，遍历数组时将每个元素映射到哈希表中，如果哈希表中已经存在这个元素则说明这就是个重复元素。因此直接使用C++ STL中的hash_set（参见《STL系列之六 set与hash_set》）可以方便的在O(n)时间内完成对重复元素的查找。

    但是题目却在空间复杂度上有限制——要求为O(1)的空间。因此采用哈希表这种解法肯定在空间复杂度上是不符合要求的。但可以沿着哈希法的思路继续思考，题目中数组中所以数字都在范围[0， n-1]，因此哈希表的大小为n即可。因此我们实际要做的就是对n个范围为0到n-1的数进行哈希，而哈希表的大小刚好为n。对排序算法比较熟悉的同学不难发现这与一种经典的排序算法——基数排序非常类似。而基数排序的时间空间复杂度刚好符合题目要求！因此尝试使用基数排序来解这道面试题。

 

    下面以2，4，1，5，7，6，1，9，0，2这十个数为例，展示下如何用基数排序来查找重复元素。

下标

  0

  1

  2

  3

  4

  5

  6

  7

  8

  9

数据

  2

  4

  1

  5

  7

  6

  1

  9

  0

  2

（1）由于第0个元素a[0] 等于2不为0，故交换a[0]与a[a[0]]即交换a[0]与a[2]得：

下标

  0

  1

  2

  3

  4

  5

  6

  7

  8

  9

数据

  1

  4

  2

  5

  7

  6

  1

  9

  0

  2

（2）由于第0个元素a[0] 等于1不为0，故交换a[0]与a[a[0]]即交换a[0]与a[1]得：

下标

  0

  1

  2

  3

  4

  5

  6

  7

  8

  9

数据

  4

  1

  2

  5

  7

  6

  1

  9

  0

  2

（3）由于第0个元素a[0] 等于4不为0，故交换a[0]与a[a[0]]即交换a[0]与a[4]得：

下标

  0

  1

  2

  3

  4

  5

  6

  7

  8

  9

数据

  7

  1

  2

  5

  4

  6

  1

  9

  0

  2

（4）由于第0个元素a[0] 等于7不为0，故交换a[0]与a[a[0]]即交换a[0]与a[7]得：

下标

  0

  1

  2

  3

  4

  5

  6

  7

  8

  9

数据

  9

  1

  2

  5

  4

  6

  1

  7

  0

  2

（5）由于第0个元素a[0] 等于9不为0，故交换a[0]与a[a[0]]即交换a[0]与a[9]得：

下标

  0

  1

  2

  3

  4

  5

  6

  7

  8

  9

数据

  2

  1

  2

  5

  4

  6

  1

  7

  0

  9

（6）由于第0个元素a[0] 等于2不为0，故交换a[0]与a[a[0]]即交换a[0]与a[2]，但a[2]也为2与a[0]相等，因此我们就找到了一个重复的元素——2。

下标

  0

  1

  2

  3

  4

  5

  6

  7

  8

  9

数据

  2

  1

  2

  5

  4

  6

  1

  7

  0

  9

 

 

    有了上面的分析，代码不难写出：

[cpp] view plaincopy
  1. //GOOGLE面试题  
  2. //一个大小为n的数组，里面的数都属于范围[0, n-1]，有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。  
  3. //By MoreWindows (http://blog.csdn.net/MoreWindows)  
  4. #include <stdio.h>  
  5. const int NO_REPEAT_FLAG = -1;  
  6. void Swap(int &x, int &y)  
  7. {  
  8.     int t = x;  
  9.     x = y;  
  10.     y = t;  
  11. }  
  12. //类似于基数排序，找出数组中第一个重复元素。  
  13. int RadixSort(int a[], int n)  
  14. {  
  15.     int i;  
  16.     for (i = 0; i < n; i++)  
  17.     {  
  18.         while (i != a[i])  
  19.         {  
  20.             if (a[i] == a[a[i]])  
  21.                 return a[i];  
  22.             Swap(a[i], a[a[i]]);  
  23.         }  
  24.     }  
  25.     return NO_REPEAT_FLAG;  
  26. }  
  27. void PrintfArray(int a[], int n)  
  28. {  
  29.     for (int i = 0; i < n; i++)  
  30.         printf("%d ", a[i]);  
  31.     putchar('\n');  
  32. }  
  33. int main()  
  34. {  
  35.     printf("    白话经典算法系列之十 一道有趣的GOOGLE面试题 \n");        
  36.     printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");   
  37.   
  38.     const int MAXN = 10;  
  39.     int a[MAXN] = {2, 4, 1, 5, 7,  6, 1, 9, 0, 2};  
  40.     //int a[MAXN] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};  
  41.   
  42.     printf("数组为: \n");  
  43.     PrintfArray(a, MAXN);  
  44.   
  45.     int nRepeatNumber = RadixSort(a, MAXN);  
  46.     if (nRepeatNumber != NO_REPEAT_FLAG)  
  47.         printf("该数组有重复元素，此元素为%d\n", nRepeatNumber);  
  48.     else  
  49.         printf("该数组没有重复元素\n");  
  50.     return 0;  
  51. }  

    运行结果如下图所示：

白话经典算法系列

    整个程序的核心代码只有短短5行左右，虽然有二重循环语句，但每个元素只会被访问一次，完成符合题目对时间复杂度的要求。

 

用基数排序来解决这道题目虽然思维巧妙，但会改动原数组的数据。有没有一种解法既找出一个重复的数据，又不改动数组中的数据了？请看《【白话经典算法系列之十一】一道有趣的GOOGLE面试题 --【解法2】》。

 

 

转载请标明出处，原文地址：http://blog.csdn.net/morewindows/article/details/8204460

欢迎关注微博：http://weibo.com/MoreWindows

另外，白话经典算法系列的电子书已经发布至第二版了，下载地址为：http://download.csdn.net/detail/morewindows/4560056

 

 

【白话经典算法系列之十二】数组中只出现1次的两个数字(百度面试题) 将介绍一道百度面试题，欢迎大家浏览。


 【白话经典算法系列之十二】数组中只出现1次的两个数字(百度面试题)

微博http://weibo.com/MoreWindows已开通，欢迎关注。

本系列文章地址：http://blog.csdn.net/MoreWindows/article/category/859207

首先来看题目要求：

在一个数组中除两个数字只出现1次外，其它数字都出现了2次， 要求尽快找出这两个数字。

    考虑下这个题目的简化版——数组中除一个数字只出现1次外，其它数字都成对出现，要求尽快找出这个数字。这个题目在之前的《位操作基础篇之位操作全面总结》中的“位操作趣味应用”中就已经给出解答了。根据异或运算的特点，直接异或一次就可以找出这个数字。

    现在数组中有两个数字只出现1次，直接异或一次只能得到这两个数字的异或结果，但光从这个结果肯定无法得到这个两个数字。因此我们来分析下简化版中“异或”解法的关键点，这个关键点也相当明显——数组只能有一个数字出现1次。

    设题目中这两个只出现1次的数字分别为A和B，如果能将A，B分开到二个数组中，那显然符合“异或”解法的关键点了。因此这个题目的关键点就是将A，B分开到二个数组中。由于A，B肯定是不相等的，因此在二进制上必定有一位是不同的。根据这一位是0还是1可以将A，B分开到A组和B组。而这个数组中其它数字要么就属于A组，要么就属于B组。再对A组和B组分别执行“异或”解法就可以得到A，B了。而要判断A，B在哪一位上不相同，只要根据A异或B的结果就可以知道了，这个结果在二进制上为1的位都说明A，B在这一位上是不相同的。

    比如int a[] = {1, 1, 3, 5, 2, 2}

    整个数组异或的结果为3^5即 0x0011 ^ 0x0101 = 0x0110

    对0x0110，第1位（由低向高，从0开始）就是1。因此整个数组根据第1位是0还是1分成两组。

    a[0] =1  0x0001  第一组

    a[1] =1  0x0001  第一组

    a[2] =3  0x0011  第二组

    a[3] =5  0x0101  第一组

    a[4] =2  0x0010  第二组

    a[5] =2  0x0010  第二组

    第一组有{1, 1, 5}，第二组有{3, 2, 3}，明显对这二组分别执行“异或”解法就可以得到5和3了。

    分析至些，相信代码不难写出，下面给出完整的源代码：

[cpp] view plaincopy
  1. // 百度面试题  
  2. //数组中除两个数字外，其它数字都出现了次。要求尽可能快的找出这两个数字  
  3. //By MoreWindows (http://blog.csdn.net/MoreWindows)  
  4. #include <stdio.h>  
  5. void FindTwoNotRepeatNumberInArray(int *a, int n, int *pN1, int *pN2)  
  6. {  
  7.     int i, j, temp;  
  8.       
  9.     //计算这两个数的异或结果  
  10.     temp = 0;  
  11.     for (i = 0; i < n; i++)  
  12.         temp ^= a[i];  
  13.       
  14.     // 找第一个为1的位  
  15.     for (j = 0; j < sizeof(int) * 8; j++)  
  16.         if (((temp >> j) & 1) == 1)  
  17.             break;  
  18.   
  19.     // 第j位为1,说明这两个数字在第j位上是不相同的  
  20.     // 由此分组即可  
  21.     *pN1 = 0, *pN2 = 0;  
  22.     for (i = 0; i < n; i++)  
  23.         if (((a[i] >> j) & 1) == 0)  
  24.             *pN1 ^= a[i];  
  25.         else  
  26.             *pN2 ^= a[i];  
  27. }  
  28. void PrintfArray(int a[], int n)  
  29. {  
  30.     for (int i = 0; i < n; i++)  
  31.         printf("%d ", a[i]);  
  32.     putchar('\n');  
  33. }  
  34. int main()  
  35. {  
  36.     printf("    白话经典算法系列之十二数组中不重复的个数字(百度面试题) \n");        
  37.     printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");   
  38.   
  39.     const int MAXN = 10;  
  40.     //int a[MAXN] = {1, 2, 7, 5, 100,  100, 6, 1, 2, 5};  
  41.     int a[MAXN] = {1, 2, 3, 4, 1,  2, 3, 4, 0, 5};  
  42.   
  43.     printf("数组为: \n");  
  44.     PrintfArray(a, MAXN);  
  45.   
  46.     int nNotRepeatNumber1, nNotRepeatNumber2;  
  47.     FindTwoNotRepeatNumberInArray(a, MAXN, &nNotRepeatNumber1, &nNotRepeatNumber2);  
  48.     printf("两个不重复的数字分别为: %d %d\n", nNotRepeatNumber1, nNotRepeatNumber2);  
  49.     return 0;  
  50. }  

运行结果如下所示：

白话经典算法系列

 

百度面试在算法这一环节上一般会出多道算法题，下次再整理几篇，欢迎大家继续参阅。

 

白话经典算法系列文章地址：

http://blog.csdn.net/MoreWindows/article/category/859207

转载请标明出处，原文地址：http://blog.csdn.net/morewindows/article/details/8214003

欢迎关注微博：http://weibo.com/MoreWindows

【白话经典算法系列之十三】随机生成和为S的N个正整数——投影法

【白话经典算法系列之十三】随机生成和为S的N个正整数——投影法 

    随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。

    以生成和为20的4个数为例，可以先生成随机生成0到20之间的三个数字再排序，假设得到了4，7，18。然后在X-Y数轴上画出这三个数，如下图：

白话经典算法系列

然后将这些数值投影到Y轴上，可得下图：

白话经典算法系列

由图很容易看出AB，BC，CD，DE这四段的长度和肯定为20。因此AB，BC，CD，DE这四段的长度即和为20的4个数，这4个数分别为4，3，11，2。

 

这种方法只要随机生成N - 1个不同数，然后排序后计算两两差值就可以得到和为S的N个正整数，因此效率还是比较高的。下面给出完整代码（随机生成N - 1个不同数可以参考《STL系列十一随机三趣题——随机重排，文件中随机取一行，生成N个随机数》）：

[cpp] view plaincopy
  1. #include <cstdio>  
  2. #include <ctime>  
  3. #include <set>  
  4. #include <algorithm>  
  5. using namespace std;  
  6. //在[s, e)区间上随机取n个数并存放到a[]中  
  7. void GetRandomNum(int *a, int n, int s, int e)  
  8. {  
  9.     std::set<int> set_a;  
  10.     srand(time(NULL));  
  11.     for (int i = e - n; i < e; i++)  
  12.     {  
  13.         int num = (rand() % i) + s;  
  14.         if (set_a.find(num) == set_a.end())  
  15.             set_a.insert(num);  
  16.         else  
  17.             set_a.insert(i);  
  18.     }  
  19.     i = 0;  
  20.     std::set<int>::iterator pos;  
  21.     for (pos = set_a.begin(); pos != set_a.end(); pos++)  
  22.         a[i++] = *pos;  
  23. }  
  24. int main()  
  25. {  
  26.     const int NSUM = 20;  
  27.     const int NCOUNT = 4;  
  28.       
  29.     printf("           生成和为%d的%d个数 \n", NSUM, NCOUNT);  
  30.     printf("--- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");    
  31.       
  32.     int    a[NCOUNT];  
  33.       
  34.     GetRandNumberInRange(a, NCOUNT - 1, 0, NSUM);  
  35.     sort(a, a + NCOUNT - 1);  
  36.     a[NCOUNT - 1] = NSUM;  
  37.   
  38.     printf("  已经生成和为%d的%d个数: \n", NSUM, NCOUNT);  
  39.     printf("%d ", a[0]);  
  40.     for (int i = 1; i < NCOUNT; i++)  
  41.         printf("%d ", a[i] - a[i - 1]);  
  42.     putchar('\n');  
  43.     return 0;  
  44. }  

运算结果如下图所示：

白话经典算法系列

 

这种“投影法”能有效解决随机生成和为S的N个正整数，其算法本质是通过“投影”得到各数据之间的长度差，而且这些长度差之和即投影线段的总长度显然会等于最大数据的值减去最小数据的值。

 

下面分析下算法的时间复杂度：

算法分为生成随机的N-1个数+排序+遍历共费时O(N * logN) +O(N * logN) + O(N)，整体时间复杂度为O(N * logN)。

算法的最主要费时操作在排序上，如果数据量不是太大，使用基数排序（见《【白话经典算法系列之十】一道有趣的GOOGLE面试题解法》）可以将排序操作的时间复杂度降低到O(N)。

其次在生成随机的N-1个数时，虽然只要调用rand()随机函数N-1次，但由于使用了set来做数据存储的容器，因此每次插入数据前的查找要费时O(logN)，插入新数据时也要费时O(logN)，可以改用hast_set来进一步提高效率（见《STL系列之六 set与hash_set》）。

 

欢迎大家讨论新颖的解法^_^，多多交流，开阔思路。

 

 

《白话经典算法系列》专栏地址：http://blog.csdn.net/morewindows/article/category/859207

转载请标明出处，原文地址：

欢迎关注微博：http://weibo.com/MoreWindows


【白话经典算法系列之十四】腾讯2012年实习生笔试加分题


地址：http://blog.csdn.net/morewindows/article/details/8742666转载请标明出处，谢谢。

欢迎关注微博：http://weibo.com/MoreWindows      

 

    之前参加2012年腾讯实习生笔试时，在考场中遇到一道加分题，当时灵光一闪，直接挥笔就解决这道题目。今天看到学校论坛上有师弟师妹们在询问这题的解法，就写篇博客来分享我的解法吧，也欢迎大家讨论其它解法。

    首先来看题目描述：

三 、加分题

28）给定一数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，不允许使用除法：

要求O（1）空间复杂度和O（n）的时间复杂度；

除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆空间和全局静态变量等）；

实现程序（主流编程语言任选）实现并简单描述。

    这道题目最为独特的要求就是除去遍历计算器外不能申请其它新的变量。怎么解决了？首先不考虑这个条件，代码如下：

[cpp] view plaincopy
  1. // 腾讯2012年实习生笔试加分题  
  2. //http://blog.csdn.net/morewindows/article/details/8742666  
  3. //By MoreWindows( http://blog.csdn.net/MoreWindows )  
  4. #include <stdio.h>  
  5. void PrintfArray(int a[], int n)    
  6. {    
  7.     for (int i = 0; i < n; i++)    
  8.            printf("%5d ", a[i]);    
  9.     putchar('\n');    
  10. }   
  11. int main()  
  12. {  
  13.     printf("    腾讯2012年实习生笔试加分题  \n");  
  14.     printf(" - http://blog.csdn.net/morewindows/article/details/8742666 -\n");  
  15.     printf(" -- By MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");   
  16.       
  17.     const int MAXN = 5;  
  18.     int a[MAXN] = {1, 3, 5, 7, 9};  
  19.     int b[MAXN];  
  20.       
  21.     printf("数组a为:\n");  
  22.     PrintfArray(a, MAXN);  
  23.   
  24.     b[0] = 1;  
  25.     int i;  
  26.     for (i = 1; i < MAXN; i++)  
  27.         b[i] = b[i - 1] * a[i - 1];  
  28.     int temp = 1;  
  29.     for (i = MAXN - 2; i >= 0; i--)  
  30.     {  
  31.         temp *= a[i + 1];  
  32.         b[i] *= temp;  
  33.     }  
  34.   
  35.     printf("数组b为:\n");  
  36.     PrintfArray(b, MAXN);  
  37.     return 0;  
  38. }  

解释下代码，设有数组大小为5。

对于第一个for循环

第一步：b[0] = 1;

第二步：b[1] = b[0] * a[0] = a[0]

第三步：b[2] = b[1] * a[1] = a[0] * a[1];

第四步：b[3] = b[2] * a[2] = a[0] * a[1] * a[2];

第五步：b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a[3];

然后对于第二个for循环

第一步

temp *= a[4] = a[4];  

b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4];

第二步

temp *= a[3] = a[4] * a[3];

b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3];

第三步

temp *= a[2] = a[4] * a[3] * a[2];  

b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2];

第四步

temp *= a[1] = a[4] * a[3] * a[2] * a[1];  

b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1];

由此可以看出从b[4]到b[0]均已经得到正确计算。

运行结果如下所示（图片无法打开？请访问http://blog.csdn.net/morewindows/article/details/8742666）：

白话经典算法系列

然后考虑到题目要求不能申请额外的临时变量，因此int temp肯定是不能有的，那用什么来代替这个temp了？很简单，用b[0]来代替即可。于是上面的第二个for循环语句变为：

[cpp] view plaincopy
  1. for (i = MAXN - 1; i >= 1; i--)  
  2. {  
  3.     b[i] *= b[0];  
  4.     b[0] *= a[i];  
  5. }  

试验下，运行结果如下所示（图片无法打开？请访问http://blog.csdn.net/morewindows/article/details/8742666）：

白话经典算法系列

呵呵，b[0]一代替，轻轻松松加分到手^_^。有其它方法欢迎交流（http://weibo.com/MoreWindows  Or morewindows@126.com），谢谢。

 

地址：http://blog.csdn.net/morewindows/article/details/8742666转载请标明出处，谢谢。

欢迎关注微博：http://weibo.com/MoreWindows      







标签：

相关文章