排序

1. 冒泡排序：比较i位置和i+1位置上的数，把较大的数放在i+1位置上，从左往右，过一遍，找出数组中的最大数排在最末尾，然后再以同样的方式，找出次大的数放在次末位置上…
   时间复杂度：O（N**2）

void BubbleSort(int *a, int len) {int i, j, temp;for (j = len - 1; j > 0; j--) {for (i = 0; i < len; i++) {if (a[i] > a[i + 1]) {swap(a, i, i + 1);}}}
}

这里的swap是一个自定义的交换函数

void swap(int *a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;
}

2. 选择排序：遍历数组，找到数组中最小的数，放到0位置，再在余下数中，找出最小的数放在1位置上，依次排好
   *时间复杂度：O(Nlog(2,N))

void SelectionSort(int *a, int len) {int i, j, minIndex;for (i = 0; i < len - 1; i++) {minIndex = i;for (j = i + 1; j < len; j++)minIndex = a[j] < a[minIndex] ? j : minIndex;//三目运算真的香，我在这抖个机灵swap(a, i, minIndex);}

3. 插入排序：从数组1位置的数开始，与其左边的数比较，小就交换，不小就不交换
   时间复杂度与样本情况有关，

void insertionSort(int*a, int len){int i;for(i=0;i<len;i++){for(int j=i-1;j>=0&&a[j]>a[j+1];j--)swap(a,j,j+1);

递归实质：

是程序帮你压栈的过程，将程序运行的所有细节都压入一个栈中，需要的时候调用子过程

归并排序：归并排序可以避免重复排序所要付出的时间代价

#include <stdio.h>
int getMax(int *arr, int L, int R){//用递归的方式求最大值if(L==R){//递归结束条件return arr[L];}int mid=(L+R)/2;//分治思想int maxLeft=getMax(arr,L,mid);找出左面的最大值int maxRight=getMax(arr,mid+1,R);//再找出右面的最大值return maxLeft>maxRight?maxLeft:maxRight;//输出最大的一个
}//归并方法
void merge_1(int *arr,int l,int mid,int r){int help[r-l+1];//辅助数组int i=0;int p1=l,p2=mid+1;while(p1<=mid&&p2<=r)//对已经排好序的两个数组进行外排help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];//两者有且必有一个越界while(p1<=mid)help[i++]=arr[p1++];while(p2<=r)help[i++]=arr[p2++];for(i=0;i<r-l+1;i++)arr[l+i]=help[i];}
void sortProcess(int *arr,int l, int r){if(r==l)return;int mid=l+(r-l)>>1;//位移运算优于四则运算sortProcess(arr,l,mid);sortProcess(arr,mid+1,r);merge_1(arr,l,mid,r);}/*小和问题：在一个数组中，每一个元素左边比当前元素值小的元素值累加起来，叫做这个数组的小和
例如：[2,3,4,1,5]
2左边比2小的元素：无
3左边比3小的元素：2
4左边比4小的元素：2，3
1左边比1小的元素：无
5左边比5小的元素：2,3,4,1
小和small_sum = 2 + 2 + 3 + 2 + 3 + 4 + 1 = 17*/int merge_2(int *a, int l, int m,int r){int help[r-l+1];int i=0;int p1=l,p2=m+1;int res=0;while(p1<=m&&p2<=r){res+=a[p1]<a[p2]?a[p1]*(r-p2+1):0;//找每一个元素右边，有几个数比它大，则它就被榨出几次，help[i++]=a[p1]<a[p2]?a[p1++]:a[p2++];}while(p1<=m)help[i++]=a[p1++];while(p2<=r)help[i++]=a[p2++];for(i=0;i<(r-l+1);i++)a[l+i]=help[i];return res;
}
int mergeSort(int*arr,int l,int r){//分治思想，左面的小和，加上右面的小和，层层归并，避免重复if(l==r)return 0;int mid=l+(r-l)>>1;//防溢出=>l+(r-l)/2,/2就是向右移一位return mergeSort(arr,l,mid)+mergeSort(arr,mid+1,r)+merge_2(arr,l,mid,r);
}
int smallSum(int *arr,int len){return mergeSort(arr,0,len-1);
}//逆序对问题int main() {int a[]={3,2,6,14,9,10};int length=sizeof(a)/ sizeof(a[0]);printf("%d\n",getMax(a,0,5));sortProcess (a, 0, 5);for(int i=0;i<6;i++)printf("%d,",a[i]);printf("\n");printf("%d\n", smallSum(a,length));return 0;
}