C++知识点（二）

发表于 | 分类于 ， | 阅读数 次
字数统计: 5.1k 字 | 阅读时长 ≈ 20 分钟

Leetcode 29. Divide Two Integers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which
could only store integers within the 32-bit signed integer range:
 [−2^31,  2^31 − 1]. For the purpose of this problem,
 assume that your function returns 2^31 − 1 when the division result overflows.

这道题目坑很多,首先被除数与除数的正负问题的坑,以及除数大于被除数的坑.
最重要且最难的坑是,INT_MIN的负数取绝对值是超过INT_MAX的,这是不允许的.还有就是时间复杂度的坑.
首先从题干中我们知道这里不能用乘除和取模,但是我们可以用+,-.这就是我知识的局限性,不仅可以用加减,事实上我们还可以用移位操作,左移一位表示×2,这是降低该题时间复杂度的最好方法.
在C++中移位分为左移和右移,分别用<<和>>来表示.

此外该题的最重要的点,是-INT_MIN>INT_MAX,当分子是-INT_MIN,分母是-1的时候,由于返回的值也必须在int范围内,所以我们可以在函数的开始时就设置一个判断,当分子是INT_MIN,分母是-1时,返回的是INT_MAX.当然还有一些情况是分子为$INT_MIN$,而分母为其他整数.最简单的方法是强制类型转换,将其转成longlong类型,当然如果不这么做,我们可以先对INT_MIN加上一个分子数,将其先缩到里面然后,再将其转成正数处理.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    typedef long long ll;

int divide(int n_, int d_) {
    ll ans=0;
    ll n=abs((ll)n_);
    ll d=abs((ll)d_);
    while(n>=d){
        ll a=d;
        ll m=1;
        while((a<<1) < n){a<<=1;m<<=1;}
        ans+=m;
        n-=a;
    }
    if((n_<0&&d_>=0)||(n_>=0&&d_<0))
        return -ans;
    if(ans>INT_MAX){
        return INT_MAX;
    }
    return ans;
}
};

快速排序

pic1

从图中可以看出:
left指针，right指针，base参照数。
其实思想是蛮简单的，就是通过第一遍的遍历（让left和right指针重合）来找到数组的切割点。

  1. 首先我们从数组的left位置取出该数（20）作为基准（base）参照物。
  2. 从数组的right位置向前找，一直找到比（base）小的数，如果找到，将此数赋给left位置（也就是将10赋给20），此时数组为：10，40，50，10，60，left和right指针分别为前后的10。
  3. 从数组的left位置向后找，一直找到比（base）大的数，如果找到，将此数赋给right的位置（也就是40赋给10），此时数组为：10，40，50，40，60，left和right指针分别为前后的40。
  4. 第四步：重复“第二,第三“步骤，直到left和right指针重合，最后将（base）插入到40的位置，此时数组值为： 10，20，50，40，60，至此完成一次排序。
  5. 第五步：此时20已经潜入到数组的内部，20的左侧一组数都比20小，20的右侧作为一组数都比20大，以20为切入点对左右两边数按照”第一，第二，第三，第四”步骤进行，最终快排大功告成。

快速排序具有最好的平均性能（average behavior），但最坏性能（worst case behavior）和插入排序.原因是快速排序希望的是能找到最中间位置的数字,但是如果它找到的是最边上的,显然,这时接下去迭代的只有一侧进行,另一侧没有数,这对于它来说很坏了.

相同，也是O(n^2)。比如一个序列5,4,3,2,1，要排为1,2,3,4,5。按照快速排序方法，每次只会有一个数据进入正确顺序，不能把数据分成大小相当的两份，很明显，排序的过程就成了一个歪脖子树，树的深度为n，那时间复杂度就成了O(n^2)。尽管如此，需要排序的情况几乎都是乱序的，自然性能就保证了。据书上的测试图来看，在数据量小于20的时候，插入排序具有最好的性能。当大于20时，快速排序具有最好的性能，归并(merge sort)和堆排序(heap sort)也望尘莫及，尽管复杂度都为nlog2(n)。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
(1) 分治法的基本思想
　分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
(2)代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<stdio.h>
void quickSort(int a[],int left,int right)
{
　　int i=left;
　　int j=right;
　　int temp=a[left];
　　if(left>=right)
　　　　return;
　　while(i!=j)
　　{
　　　　while(i<j&&a[j]>=temp)
　　　　j--;
　　　　if(j>i)
　　　　　　a[i]=a[j];//a[i]已经赋值给temp,所以直接将a[j]赋值给a[i],赋值完之后a[j],有空位
　　　　while(i<j&&a[i]<=temp)
　　　　i++;
　　　　if(i<j)
　　　　　　a[j]=a[i];
　　}
　　a[i]=temp;//把基准插入,此时i与j已经相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
　　quickSort(a,left,i-1);/*递归左边*/
　　quickSort(a,i+1,right);/*递归右边*/
}

int main()
{
int a[9]={8,2,6,12,1,9,5,5,10};
int i;
quickSort(a,0,8);/*排好序的结果*/
for(i=0;i<8;i++)
printf("%4d",a[i]);
getchar();
return 0;
}

归并排序

归并排序（Merge Sort）与快速排序思想类似：将待排序数据分成两部分，继续将两个子部分进行递归的归并排序；然后将已经有序的两个子部分进行合并，最终完成排序。其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序，但是归并排序是一种稳定的排序算法，快速排序则不然。

所谓稳定排序，表示对于具有相同值的多个元素，其间的先后顺序保持不变。对于基本数据类型而言，一个排序算法是否稳定，影响很小，但是对于结构体数组，稳定排序就十分重要。例如对于student结构体按照关键字score进行非降序排序：

数组的归并排序

归并排序的思想实际上是一种分治法，即将待排序数据分成两部分，分别对两部分排序，然后将这两部分合并。下面以非降序排序为例：

1
2
3
4
5
6
7
8
9
10
11
// Split arr[] into two parts [begin,mid), [mid,end)
// and using merge_core to merge this two parts
// Total Time O(nlogn)
void merge_sort(int arr[], int begin, int end)
{
    if (end-begin < 2) return;
    int mid = (begin+end)>>1;
    merge_sort(arr,begin,mid);
    merge_sort(arr,mid,end);
    merge_core(arr,begin,mid,end);
}   // Time O(logn)

注意归并排序归并的前提是两子序列已经有了顺序,只要在归并时将这两个子序列并成一个大的有序序列即可,这就是为什么merge_sort在merge_core的前面.

其中arr[]为待排序数组，对于一个长度为N的数组，直接调用merge_sort(arr,0,N);则可以排序。

归并排序总体分为两步，首先分成两部分，然后对每个部分进行排序，最后合并。当然也可以分成三部分或其他，然而通常是分成两部分，因此又称为二路归并。merge_core可以将两个有序数组合并成一个，具体操作如图所示：
pic2

链表的归并排序

事实上，归并排序更适合对链表排序，因为在合并两个链表时，不需要额外的辅助空间存储，而且也不需要对数据拷贝，直接移动指针即可。唯一的不便是：需要每次寻找到链表的中间节点，然后以此将该链表分割成两部分。寻找中间节点，可以定义两个指针fast和Mid，fast每次移动两步，mid每次移动一步，当fast到链表尾部时，mid此时处于链表中间（不用考虑奇偶情况）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Merge sort for single list as ascending order
// single list node define
typedef struct __ ListNode
{
    int val;
    struct __ListNode * next;
}ListNode;

// Merge sort for single list without head node
ListNode *merge_sort(ListNode *head)
{
    if (head==NULL || head->next==NULL) return head;
    ListNode * fast, * mid, H;
    // find mid node between head and end
    for (H.next=head, fast=mid=&H; fast && fast->next;){
        mid = mid->next;
        fast = fast->next->next;
    }
    fast = mid->next;
    mid->next = NULL;    // cut down mid part from head list
    mid = fast;

    head = merge_sort(head);
    mid = merge_sort(mid);
    return merge_core(head,mid);
}

注意，找到链表的中间节点后，务必将其指向NULL，以保证确实将链表分成两部分。然后将两个链表head与mid进行合并。由于合并后可能会修改链表头结点，因此要返回新的链表头结点。下面是合并操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// merge single list without head node (ascending order)
ListNode *merge_core(ListNode *i, ListNode *j)
{
    ListNode H, * p;
    for (p=&H; i && j; p=p->next){
        if (i->val < j->val){
            p->next = i;
            i = i->next;
        }
        else{
            p->next = j;
            j = j->next;
        }
    }
    p->next = (i ? i:j);
    return H.next;
}

链表合并时，不需要像数组那样，直接可以将链表尾部p->next指向剩余的i或j,即可完成合并。可以看出，归并排序更适合于对链表排序，而快速排序适合于数组排序。

归并排序时间复杂度和稳定性

归并排序的时间复杂度是O(NlgN)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(NlgN)。

归并排序稳定性
归并排序是稳定的算法，它满足稳定算法的定义。
算法稳定性 — 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

冒泡排序

算法思想：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
    pic3
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}

改进

1）设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BubbleSort2(int a[], int n)
{
       int j, k;
       bool flag;

       k = n;
       flag = true;
       while (flag)
       {
              flag = false;
              for (j = 1; j < k; j++)
                     if (a[j - 1] > a[j])
                     {
                            Swap(a[j - 1], a[j]);
                            flag = true;
                     }
              k--;
       }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void BubbleSort3(int a[], int n)
{
       int j, k;
       int flag;

       flag = n;
       while (flag > 0)
       {
              k = flag;
              flag = 0;
              for (j = 1; j < k; j++)
                     if (a[j - 1] > a[j])
                     {
                            Swap(a[j - 1], a[j]);
                            flag = j;
                     }
       }
}

直接插入排序

算法思想:
直接插入排序(Straight Insertion Sort)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 void insert_sort(int a[], int n)
{
    int i, j, k;

    for (i = 1; i < n; i++)
    {
        //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
        for (j = i - 1; j >= 0; j--)
            if (a[j] < a[i])
                break;

        //如找到了一个合适的位置
        if (j != i - 1)
        {
            //将比a[i]大的数据向后移
            int temp = a[i];
            for (k = i - 1; k > j; k--)
                a[k + 1] = a[k];
            //将a[i]放到正确位置上
            a[k + 1] = temp;
        }
    }
}

pic4

直接插入排序的时间复杂度和稳定性

直接插入排序时间复杂度
直接插入排序的时间复杂度是O(N2)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，直接插入排序的时间复杂度是O(N2)。

直接插入排序稳定性
直接插入排序是稳定的算法，它满足稳定算法的定义。
算法稳定性 — 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

简单选择排序

每一趟从待排序的数据元素中选出最小（最大）的元素，顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void select_sort(int a[],int n)
{
	int i,j,min;
    for(int i=0;i<n-1;i++)//i为已排序序列的末尾
	{
        min=i;
        for(int j=i+1;j<n;j++)//未排序序列
            if(a[j]<a[min])//找出未排序序列中的最小值
                min=j;
        if(min!=i)
            swap(a[i],a[min]);//放到已排序序列的末尾，该操作很有可能把稳定性打乱，所以选择排序是不稳定的排序算法
    }
}

数据结构：数组
稳定性：不稳定

时间复杂度

最差时间复杂度：O(n^2)
最优时间复杂度：O(n^2)
平均时间复杂度：O(n^2)
所需辅助空间：O(1)

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
pic5
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
pic6
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序基本思想及步骤：
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

  1. 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
    a. 假设给定无序序列结构如下
    pic7
    1）. 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
    pic8
    2）. 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
    pic9
    3）这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
    pic10
    此时，我们就将一个无需序列构造成了一个大顶堆。
  2. 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
    pic11
    pic12
    pic13

再简单总结下堆排序的基本思路：

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/堆排序
void HeapSort(int A[], int N)
{
    int i;
    //步骤一：根据A数组元素，创建大根堆
    //从第 n/2 个记录开始进行建堆
    for (i = N / 2; i >= 0; i--)
    {
        PercDown(A, i, N);
    }

    //步骤二：调整大根堆
    for (i = N - 1; i > 0; i--)
    {
        //首尾交换
        Swap(&A[0], &A[i]);
        //将最后一个叶子节点与根节点进行交换，
        //再根据堆性质进行调整
        PercDown(A, 0, i);
    }
}
//给定父节点的索引，得到左子节点的索引,跟的索引为0
#define LeftChild(i) (2*(i)+1)

//元素向下调整方法
void PercDown(int A[], int i, int N)
{
    //子节点的索引号
    int child;
    //存储当前父节点元素的临时变量
    //(注：每一个节点都可以看作是其子树的根节点)
    int tmp;

    for (tmp = A[i]; LeftChild(i)<N; i = child)
    {
        child = LeftChild(i); //左子节点索引
        //挑选出左、右子节点中较大者
        if (child != N - 1 && A[child + 1] > A[child])
        {
            child++;
        }

        //比较当前父节点与较大子节点
        if (A[i]<A[child])
        {
            //交换当前父节点处的元素值与较大子节点的元素值
            //此处也可以调用：Swap(A[i], A[child])
            tmp = A[i];
            A[i] = A[child];
            A[child] = tmp;
        }
        else
        {
            break;
        }
    }
}

总结

1、堆排序最大的优点就是，在最坏的情况下，时间复杂度仍为 O(n*logn)；
2、堆排序只需要存放一个记录的辅助空间，所以堆排序也称原地排序；
3、堆排序是不稳定的；
4、不适用于待排序数n较小的情况，但对n较大的文件还是很有效的；
5、堆排序可以通过树形结构保存部分比较结果，减少比较次数。

希尔排序

排序算法总结

pic14

C++的三元运算符？；

1
2
3
4
if (条件表达式)
    result = 表达式1;
else
    result = 表达式2;
1
2
3
4
5
int result;
int first=10;
int second=20;
result=first>second?0:1;
//执行结果：如果first>second  result=0,如果first<second result=1;

但是考题会考

1
2
3
4
5
6
7
8
9
10
using namespace std;
int main(){
int a=-1;
a = -6 ? 0 : 1;
cout<<a;
return 0;
}

//这里不是判断语句,而是一个数值(-6),则会返回true;
// 但是如果这个数值是0,则会返回false;

编译出错——++(a++)

当执行++(a++)时会编译出错.
++a往往先于a++执行,但是这里要执行++a必须要先a++,则出错了

-------------本文结束感谢您的阅读-------------