排序算法

选择排序、冒泡排序、插入排序三种排序算法可以总结为如下：
都将数组分为已排序部分和未排序部分。
选择排序将已排序部分定义在左端，然后选择未排序部分的最小元素和未排序部分的第一个元素交换。
冒泡排序将已排序部分定义在右端，在遍历未排序部分的过程执行交换，将最大元素交换到最右端。
插入排序将已排序部分定义在左端，将未排序部分元的第一个元素插入到已排序部分合适的位置。
1、选择排序
【选择排序】：最值出现在起始端
第1趟：在n个数中找到最小(大)数与第一个数交换位置
第2趟：在剩下n-1个数中找到最小(大)数与第二个数交换位置
重复这样的操作...依次与第三个、第四个...数交换位置
第n-1趟，最终可实现数据的升序（降序）排列。

void selectSort(int *arr, int length) {
    for (int i = 0; i < length - 1; i++) { //趟数
        for (int j = i + 1; j < length; j++) { //比较次数
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

2、冒泡排序
【冒泡排序】：相邻元素两两比较，比较完一趟，最值出现在末尾
第1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n个元素位置
第2趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n-1个元素位置
…… ……
第n-1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第2个元素位置

void bublleSort(int *arr, int length) {
    for(int i = 0; i < length - 1; i++) { //趟数
        int tag = 0;
        for(int j = 0; j < length - i - 1; j++) { //比较次数
            if(arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                tag = 1;
            }
        }
        if(tag == 0) {//如没有交换过，则已经有序
           return;
        } 
    }
}

3、插入排序
【插入排序】：将第i趟排序中的第i个元素插入到一个排好序的子序列中，若是由小到大排序，则将元素temp=a[i]插入到子序列a[0],a[1]…a[[i-1]中，将比a[i]元素大的数往后移动，直到找到插入的位置。

//插入排序 
void InsertSort(int *arr,int len) 
{ 
  for(int i=1;i<len;i++) 
  { 
    int j=i-1; 
    int temp=arr[i];//需要插入的数据 
    while(temp<arr[j] && j>=0)//当插入的数据小于前面的数据时 
    { 
      arr[j+1]=arr[j];//将插入的数据的后面的数据向后移动 
      j--; 
    } 
    arr[++j]=temp;//插入数据 
  } 
} 

4、希尔排序
【希尔排序】：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

1.png

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

2.png

void shellsort(int *arr, int len)  
{  
    int i, j, gap;  //gap是分组的步长
    for (gap = len / 2; gap > 0; gap /= 2) //比较的趟数
        for (i = 0; i < gap; i++)        //直接插入排序  
        {  
            for (j = i + gap; j < len; j += gap)   //单独一次的插入排序
                if (arr[j] < arr[j - gap])  
                {  
                    int temp = arr[j];  //希尔排序是在直接插入排序的基础上实现的,所以仍然需要哨兵
                    int k = j - gap;  
                    while (k >= 0 && arr[k] > temp)  
                    {  
                        arr[k + gap] = arr[k];  
                        k -= gap;  
                    }  
                    arr[k + gap] = temp;  
                }  
        }  
}  

5、快速排序
【快速排序】：
1）i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2）j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中，i++
3）i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中，j--
4）再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

//快速排序
void quick_sort(int *arr, int l, int r)
{
    if (l < r)
    {
        int i = l, j = r, x = arr[l];
        while (i < j)
        {
            while(i < j && arr[j] >= x) // 从右向左找第一个小于x的数
                j--;  
            if(i < j) 
                arr[i++] = arr[j];
            
            while(i < j && arr[i] < x) // 从左向右找第一个大于等于x的数
                i++;  
            if(i < j) 
                arr[j--] = arr[i];
        }
        arr[i] = x;
        quick_sort(arr, l, i - 1); // 递归调用 
        quick_sort(arr, i + 1, r);
    }
}

6、折半查找
【折半查找】：优化查找时间（不用遍历全部数据）
1） 数组必须是有序的
2） 必须已知min和max（知道范围）
3） 动态计算mid的值，取出mid对应的值进行比较
4） 如果mid对应的值大于要查找的值，那么max要变小为mid-1
5） 如果mid对应的值小于要查找的值，那么min要变大为mid+1

// 已知一个有序数组, 和一个key, 要求从数组中找到key对应的索引位置
int findKey(int *arr, int length, int key) {
    int min = 0, max = length - 1, mid;
    while (min <= max) {
        mid = (max - min) / 2 + min; // 直接使用(max + min) / 2 可能导致溢出
        if (key > arr[mid]) {
            min = mid + 1;
        } else if (key < arr[mid]) {
            max = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

7、求最大公约数

/** 1.直接遍历法 */
int maxCommonDivisor(int a, int b) {
    int max = 0;
    for (int i = 1; i <=b; i++) {
        if (a % i == 0 && b % i == 0) {
            max = I;
        }
    }
    return max;
}
/** 2.辗转相除法 */
int maxCommonDivisor(int a, int b) {
    int r;
    while(a % b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return b;
}

// 扩展：最小公倍数 = (a * b)/最大公约数

8、不用中间变量,用两种方法交换A和B的值

// 1.中间变量
void swap(int a, int b) {
   int temp = a;
   a = b;
   b = temp;
}

// 2.加法
void swap(int a, int b) {
   a = a + b;
   b = a - b;
   a = a - b;
}

// 3.异或（相同为0，不同为1. 可以理解为不进位加法）
void swap(int a, int b) {
   a = a ^ b;
   b = a ^ b;
   a = a ^ b;
}

9、模拟栈操作

#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
//保护全局变量：在全局变量前加static后，这个全局变量就只能在本文件中使用
static int data[1024];//栈最多能保存1024个数据
static int count = 0;//目前已经放了多少个数(相当于栈顶位置)

//数据入栈 push
void push(int x){
    assert(!full());//防止数组越界
    data[count++] = x;
}
//数据出栈 pop
int pop(){
    assert(!empty());
    return data[--count];
}
//查看栈顶元素 top
int top(){
    assert(!empty());
    return data[count-1];
}
//查询栈满 full
bool full() {
    if(count >= 1024) {
        return 1;
    }
     return 0; 
}
//查询栈空 empty
bool empty() {
    if(count <= 0) {
        return 1;
    }
    return 0;
}

int main(){
    //入栈
    for (int i = 1; i <= 10; i++) {
        push(i);
    }
    //出栈
    while(!empty()){
        printf("%d ", top()); //栈顶元素
        pop(); //出栈
    }
    printf("\n");
    return 0;
}

10、阶层
【阶层】：
（1）退出条件：参数为0或者1的时候，返回1
（2）递归：n * f(n-1)
判断一下参数，不要太大，否则程序会傻掉的（数值越界）

int factorial(int n) {
    if (n > 100) {
        return -1; // 太大了，算不出来，会越界
    }
    if (n == 1 || n ==0 ) {
        return 1;
    }
    return n * factorial(n - 1);
}

11、判断质数
质数又称素数。一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数；否则称为合数。
1）改进的直观判断法
一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数

int isPrime(int n) {//返回0是质数，否则为合数
    for(int i = 2; i <= sqrt(n); i++) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

2）
首先看一个关于质数分布的规律：大于等于5的质数一定和6的倍数相邻，例如5和7，11和13,17和19等等（反过来不成立）。
证明：令x≥1，将大于等于5的自然数表示如下：
······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。那么此时判断质数num可以以i为6个单元快进，即将方法1）循环中i++步长加大为6，加快判断速度。
而且6x-1和6x+1的非素数一定是只能是6x-1和6x+1的倍数（前后部分的x具体值不一样）。
证明：对于循环中6x-1，6x，6x+1, 6x+2，6x+3，6x+4，其中如果能被6x，6x+2，6x+4整除，则num至少得是一个偶数，但是6x-1或6x+1的形式明显是一个奇数，故不成立；另外，如果num能被6x+3或者6x整除，则num明显也能被3整除，6x-1或6x+1明显也不成立。综上，循环中只需要考虑6x-1和6x+1的情况，即循环的步长可以定为6，每次判断循环变量i和i+2的情况即可
代码如下：

int isPrime_3(int num)
{
    //两个较小数另外处理
    if(num == 2 || num == 3)
        return 1 ;
    //不在6的倍数两侧的一定不是质数
    if(num % 6 != 1&& num % 6 != 5)
        return 0;
    int tmp = sqrt(num);
    //在6的倍数两侧的也可能不是质数
    for(int i = 5;i <= tmp; i+=6 ) {
        if(num % i == 0 || num % (i + 2) == 0)
            return 0 ;
    }
    //排除所有，剩余的是质数
    return 1 ;
}

12、字符串逆序输出

void reverse(char s[]) {
    // p指向字符串头部
    char *p = s ;
    // q指向字符串尾部
    char *q = s ;
    while('\0' != *q) {
        q++ ;
    }
    q-- ;
    // 交换并移动指针，直到p和q交叉
    while(q > p) {
        char t = *p;
        char m = *q;
        *p = m;
        *q = t;
        p++;
        q--;
    }
}

13、合并排序
【合并排序】：
1)将所要进行的排序序列分为左右两个部分，如果要进行排序的序列的起始元素下标为first，最后一个元素的下标为last，那么左右两部分之间的临界点下标mid=(first+last)/2，这两部分分别是A[first … mid]和A[mid+1 … last]。
2)将上面所分得的两部分序列继续按照步骤(1)继续进行划分，直到划分的区间长度为1。
3)将划分结束后的序列进行归并排序，排序方法为对所分的n个子序列进行两两合并，得到n/2或n/2+l个含有两个元素的子序列，再对得到的子序列进行合并，直至得到一个长度为n的有序序列为止。下面通过一段代码来看如何实现归并排序。
具体操作流程：
先对所要进行排序的序列进行分解，直到分为单个元素为止，然后将其进行两两合并。由于最终分解成单个元素，因此在合并的时候.将小数放在前面，大数放在后面，得到一个有序序列。接下来对两个相连的有序序列进行排序，先比较有序序列中的第一个元素，将较小的元素放入临时数组中，接着将较小元素所在数组的下一个元素与另一个数组中的较小元素比较，同样将较小元素放入临时数组中，依次进行，直到两个数组的所有元素都放入临时数组中，最后再将临时数组的元素放入原始数组中的对应位置。

1-140I1210943V7.png

#include <stdio.h>
#include <stdlib.h>
#define N 7

void merge(int arr[], int low, int mid, int high){
    int i, k;
    int *tmp = (int *)malloc((high-low+1)*sizeof(int));
    //申请空间，使其大小为两个
    int left_low = low;
    int left_high = mid;
    int right_low = mid + 1;
    int right_high = high;
    for(k=0; left_low<=left_high && right_low<=right_high; k++){  // 比较两个指针所指向的元素
        if(arr[left_low]<=arr[right_low]){
            tmp[k] = arr[left_low++];
        }else{
            tmp[k] = arr[right_low++];
        }
    }
    if(left_low <= left_high){  //若第一个序列有剩余，直接复制出来粘到合并序列尾
    //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
    for(i=left_low;i<=left_high;i++)
        tmp[k++] = arr[i];
    }
    if(right_low <= right_high){
    //若第二个序列有剩余，直接复制出来粘到合并序列尾
    //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
        for(i=right_low; i<=right_high; i++)
            tmp[k++] = arr[i];
    }
    for(i=0; i<high-low+1; i++)
        arr[low+i] = tmp[i];
    free(tmp);
    return;
}

void merge_sort(int arr[], unsigned int first, unsigned int last){
    int mid = 0;
    if(first<last){
        mid = (first+last)/2; /* 注意防止溢出 */
        /*mid = first/2 + last/2;*/
        //mid = (first & last) + ((first ^ last) >> 1);
        merge_sort(arr, first, mid);
        merge_sort(arr, mid+1,last);
        merge(arr,first,mid,last);
    }
    return;
}

int main(){
    int i;
    int a[N]={32,12,56,78,76,45,36};
    printf ("排序前 \n");
    for(i=0;i<N;i++)
        printf("%d\t",a[i]);
    merge_sort(a,0,N-1);  // 排序
    printf ("\n 排序后 \n");
    for(i=0;i<N;i++)
        printf("%d\t",a[i]); printf("\n");
    return 0;
}

14、单链表逆序

struct ListNode
{
    int  data;
    struct  ListNode  *next;
};
typedef  ListNode  *LinkList;
ListNode *reverseListNode(ListNode *head) {//头插法
    if (head == NULL) {
        return head;
    }
    ListNode * rear,*h;//rear指向的是未排序部分的第一个结点，h指向的是已排序部分的第一个结点
    rear = head;
    h = NULL;
    while (rear) {
        ListNode *rNext = rear -> next;
        rear -> next = h;
        h = rear;
        rear = rNext;
    }
    return h;
}

15、给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符？如“abaccddeeef”,字符是b。
算法思想：要达到这个目的，我们需要 一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。在常用的 数据容器中，哈希表正是这个用途。
由于字符（char）是一个长度为8的数据类型，因此总共有可能256 种可能。于是我们创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256，以字符ASCII码为键值的哈希表。（并不仅限于英文字符，所以这里要考虑256种可能）。
我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。

#include <stdio.h>
char firstNotRepeatingChar(char* pString)
{
    //输入不合法
    if(!pString)
        return 0;
    
    //创建一个哈希表，并初始化
    const int tableSize = 256;
    int hashTable[tableSize];
    for(int i = 0; i < tableSize; i++)
        hashTable[i] = 0;
    
    //确定字符串中每个字符出现的次数
    char* pHashKey = pString;
    while(*(pHashKey) != '\0')
        hashTable[*(pHashKey++)]++;
    
    //找到字符串中只出现一次的那个字符
    pHashKey = pString;
    while(*pHashKey != '\0')
    {
        if(hashTable[*pHashKey] == 1)
            return *pHashKey;
        pHashKey++;
    }
    
    //如果这个字符串为空，或者字符串中的每个字符都至少出现两次
    return 0;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    char str[1000];
    printf("请输入字符串：");
    gets(str);//在终端输出寻找的字符串
    if(firstNotRepeatingChar(str)==0)
        printf("输入字符串中没有找到第一个只出现一次的字符！\n");
    else
        printf("输入字符串中第一个只出现一次的字符为：%c\n",firstNotRepeatingChar(str));
    
    return 0;
}

扩展成返回符合上述要求的字符下标

#include <stdio.h>
char firstNotRepeatingChar(char* pString)
{
    //输入不合法
    if(!pString)
        return -1;
    
    //创建一个哈希表，并初始化
    const int tableSize = 256;
    int hashTable[tableSize];//统计字符出现的次数
    int index[tableSize];//标记字符第一次出现所在的位置
    int j = -1;
    
    for(int i = 0; i < tableSize; i++) {
        hashTable[i] = 0;
        index[i] = -1;
    }
    
    //确定字符串中每个字符出现的次数
    char* pHashKey = pString;
    
    while(*(pHashKey) != '\0') {
        j++;
        char currentChar = *pHashKey;
        int count = ++hashTable[*(pHashKey++)];
        if (count == 1) {
            index[currentChar] = j;
        }
    }
    
    //找到字符串中只出现一次的那个字符
    pHashKey = pString;
    while(*pHashKey != '\0')
    {
        if(hashTable[*pHashKey] == 1)
            return index[*pHashKey];
        pHashKey++;
    }
    
    //如果这个字符串为空，或者字符串中的每个字符都至少出现两次
    return -1;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    char str[1000];
    printf("请输入字符串：");
    gets(str);
    if(firstNotRepeatingChar(str)==-1)
        printf("输入字符串中没有找到第一个只出现一次的字符！\n");
    else
        printf("输入字符串中第一个只出现一次的字符下标为：%d\n",firstNotRepeatingChar(str));
    
    return 0;
}

16、统计整数二进制表示中1的个数
原理：一个数减去1，则这个数的二进制数中最后一个1及其后的数字取反。x & (x - 1) 为它的二进制数中少一个1。
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

int countOne2(int num)  
{  
    int count = 0;  
    while ( num )  
    {  
        num &= (num - 1) ;  
        ++count;      
    }  
      
    return count;  
}  

17、一个楼梯有N个台阶，小明从台阶最低层地面上楼梯，小明一次可最大跨3阶（每次迈步可以跨1阶、2阶、3阶），问小明爬上顶一共有多少种步伐组合？
算法思想：设n阶台阶的走法数为f(n)。如果只有1个台阶，走法有1种（一步上1个台阶），即f(1)=1；如果有2个台阶，走法有2种（一种是上1阶，再上1阶，另一种是一步上2阶），即f(2)=2；如果有3个台阶，走法有4种（一种每次1阶，共一种；另一种是2+1，共两种；第三种是3，共1种），即f(3)=4；当有n个台阶（n>3）时，我们缩小问题规模，可以这样想：最后是一步上1个台阶的话，之前上了n-1个台阶，走法为f(n-1)种，而最后是一步上2个台阶的话，之前上了n-2个台阶，走法为f(n-2)种，而最后是一步上3个台阶的话，之前上了n-3个台阶，走法为f(n-3)种，故而f(n)=f(n-1)+f(n-2)+f(n-3)。

#include <iostream>
using namespace std;
void Circul(const int n){
    
    int i;
    int a[100];
    a[1]=1;
    a[2]=2;
    a[3]=4;
    
    if (n==1){
        cout<<a[1]<< endl;
        return;
    }else if(n==2){
        cout<< a[2]<<endl;
        return;
    }else if(n==3){
        cout<< a[3]<<endl;
        return;
    }else for(i=4;i<=n;i++){
        a[i]=a[i-3]+a[i-2]+a[i-1];
    }
    cout<< a[n]<<endl;
}

int main(int argc, const char * argv[]) {
    int n;
    cout << "请输入台阶数。。。。"<<endl;
    cin >> n;
    Circul(n);
}