首先总结以下Java和C、C++中的一般控制台输入方式，方便以后的编程题：
- java键盘输入
import java.util.Scanner;
//…………
Scanner scan = new Scanner(System.in);
String s = scan.nextLine();
int a = scan.nextInt();
int b = scan.nextInt();
String s2 = scan.next();
//…………
while(scan.hasNext()){
// 这里，循环不会随着任何输入而停止，除非输入终止操作“ctrl+Z” 或“ctrl+C”等。
}
- java读文件（会自动结束读取）
import java.util.Scanner;
//…………
Scanner scan;
try {
FileInputStream fis = new FileInputStream(new File("/home/androidjp/file.txt"));//Ubuntu下的文件路径
scan = new Scanner(fis, "utf-8");
while(scan.hasNext()){
///读取里面的信息
}
//…………
} catch (FileNotFoundException e) {
e.printStackTrace();
}
- C 输入输出（数字和字符串、文件读取）
#include <stdio.h>
#include <stdlib.h>
int main(){
freopen("D:\\file.txt", "r", stdin);//打开文件，自动填充下面要输入的数据。
//..........
scanf("%d", &a);///输入一个整数
scanf("%c", &ch); //输入一个char字符
scanf("%s" , s);///输入一串字符（遇到空格或者换行自动认为输入完毕）
ch = getchar();//输入一个char字符
getchar();//一般用于接收上一行输入完字符串后输入的换行
gets(s); //输入一串字符（遇到换号才认为输入完毕）
//.........
printf("%d\n%s" , a, s);///输入+换行
}
- C++输入输出（数字和字符串）
#include <iostream>
using namespace std;
int main(){
string s; //封装起来的字符串
char chs[5];//字符串（原始模样）
int a;
cin >> s >> a;///输入字符串 + 空格/换行 + 输入数字（如果输入了‘abc def 123’，那么，s=‘abc’ ，a=‘0’）
cin >> chs;
//........
cout << s << " , " << a << " , " << chs << endl; ///串连起来输出（endl为换行）
cout << s[2]; //输出 字符串 s 的第三个字符。
}
一、字符串匹配
KMP算法
题型：大字符串（长度为n）中，是否存在子字符串（长度为m，m<=n）？
KMP算法思路：利用一个O(m)的预处理，将匹配的复杂度降为O(n+m)。利用int[] 类型的next数组，去预处理这个需要匹配的子串，将子串中每一个元素b[i] 前面的字符串段的前缀和后缀的最大共有字符个数记录为next[i]，这样，通过这个辅助数组next[i] ，b[j] 与 a[i]如果不匹配，那么，就可以让 j 回溯到next[j] ，从而让 与后缀完全匹配的前缀的后一个元素b[新的j] 去与a[i] 进行匹配。
- Java实现：
import java.util.Scanner; /** * KMP字符串匹配算法：实际上是根据不匹配字符位置之前的字串的前缀和后缀相同的最大长度，根据这个长度，去一次移动子串多位，以达到O(n+m)的复杂度 * 步骤： * 1. 获取子串上每一个位置之前的字符串的前后缀的最大相同长度。 * 2. 让大串和子串比较，每次比较途中遇到不匹配的字符，就根据“j = next[j]”去让大串中的第i个字符与子串中第j个字符比较，模拟子串后移的过程 * Created by androidjp on 16-8-4. */ public class KMP { /** * 获取next数组 * @param b * @return */ public static int[] getNext(String b){ int j = 0; int len = b.length(); int[] next = new int[len+1]; next[0] = next[1] = 0; for(int i=1;i<b.length();i++){ while(j>0 && b.charAt(i)!=b.charAt(j)) j = next[j]; if(b.charAt(i) == b.charAt(j)) j++; next[i+1] = j; } return next; } public static void match(String a, String b, int[] next){ int j = 0; for(int i=0;i<a.length();i++){ while(j>0 && a.charAt(i)!=b.charAt(j)) j = next[j]; if (a.charAt(i) == b.charAt(j)) j++; if (j == b.length()){ System.out.println(i+1-j);///输出完全匹配时i的初始位置（因为这时i=a.length-1, 而j=b.length ，所以i要加一） return; } } System.out.println("-1"); } public static void main(String[] args){ Scanner scan = new Scanner(System.in); String a,b; while(scan.hasNext()){ a = scan.next(); b = scan.next(); match(a, b, getNext(b)); } } } - C 实现：
///这里，可以利用数组的第一个元素来记录字符串的长度，以下就是另一种写法，但思路一致。 #include "stdio.h" #include "stdlib.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASLBLE -1 #define OVERFLOW -2 #define MAXSTRLEN 255 //用户可在255以内定义最大串长 typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度 void get_next(SString T,int next[]) { int i=1,j=0; next[1]=0; while(i<=T[0]) if(j==0||T[i]==T[j]) { i++; j++; if(T[i]==T[j]) next[i]=next[j]; else next[i]=j; } else j=next[j]; } int Index_KMP(SString S,SString T) { int next[255]; int i=0; int j=0; get_next(T,next); while(i<=S[0]&&j<=T[0]) if(j==0||S[i]==T[j]) { j++; i++; } else j=next[j]; if(j>T[0]) return i-T[0]; else return 0; } int main() { SString T,S; int i,j,n; char ch; int pos; // freopen("case.txt","r",stdin); scanf("%d",&n); // 指定n对需进行模式匹配的字符串 ch=getchar(); for(j=1; j<=n; j++) { ch=getchar(); for( i=1; i<=MAXSTRLEN&&(ch!='\n'); i++) // 录入主串 { S[i]=ch; ch=getchar(); } S[0]=i-1; // S[0]用于存储主串中字符个数 ch=getchar(); for( i=1; i<=MAXSTRLEN&&(ch!='\n'); i++) // 录入模式串 { T[i]=ch; ch=getchar(); } T[0]=i-1; // T[0]用于存储模式串中字符个数 pos=Index_KMP(S,T); printf("%d\n",pos); } return 0; }
二、排序
快排（QuickSort）
- 思路：改进版的冒泡排序，采用（取基准值-交换排序-递归）的一个过程。
- 写法：一般是三个函数：①quickSort(int[] arr) 【入口函数】 ②quickSort(int[] arr, int first, int last) 【递归调用函数】 ③ partition(int[] arr, int first, int last) 【获取随机基点（可以随机，可以取中间）并实际交换排序过程函数】
- 时间复杂度：
- 平均：O(nlogn)
- 最好：O(n)
- 最坏：O(n平方)【数组本身有序 + 每次取最后一个数字作为基准】
- 空间复杂度：
- 平均：O(logn)
- 最好：O(logn)【n个元素，则递归树的高度为logn】
- 最坏：O(n) 【此时需要n-1次递归调用】
- 稳定性：不稳定
- Java写法：
/** * 快速排序 */ public static void quickSort(int[] data) { quickSort(data, 0, data.length-1); } private static void quickSort(int[] data, int first, int last) { if(first < last){//只要有两个以上的元素 int privotIndex = partition(data, first, last); quickSort(data, first,privotIndex-1); quickSort(data, privotIndex+1, last); } } private static int partition(int[] data, int first, int last) { int pivot = data[first];///取第一个元素为基准 // int pivot = randomInRange(first,last); ///或者随机取一个元素 // 然后与第一个元素交换 // int t = data[pivot]; // data[pivot] = data[first]; // data[first] = t; int low = first +1; int high = last; while(low < high){ /** * 1. 找左侧比基准大的值 */ while(low <= high && data[low]<= pivot){ low++; } /** * 2. 找右侧比基准小的值 */ while (low <= high && data[high]>pivot){ high--; } /** * 3. 交换 */ if (low < high){ int temp = data[low]; data[low] = data[high]; data[high] = temp; } } /*** * 所有交换完毕后，需要将这个基准点插入到一个适当的位置 */ while(high > first && data[high]>=pivot){ high--; } ///找到了交换点 if (pivot > data[high]){ data[first] = data[high]; data[high] = pivot; return high; }else{///不用交换，表示这一次交换后，数组基本就是有序了 return first; } } /** * 随机取值 */ private static int randomInRange(int start, int end) { return new Random().nextInt(end-start+1)+start; }
归并排序（MergeSort）
- 思路：利用辅助数组，进行一个“分治 - 合并” 的过程。与快排不同，快排是‘一边分一边执行交换排序’，而归并排序是‘拆分，进行比较排序，排了再合并’。每次拆分，用到两个部分的辅助数组，每次合并，用到一个长的辅助数组，所以多用了O(2N)的空间。
- 写法：一般分两个函数：①mergeSort(int[] arr)【递归分治主函数】②merge(int[] a,int[] b) 【合并函数】
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
- 稳定性：稳定
- Java写法：
/** * 归并排序 */ public static void mergeSort(int[] data) { ///递归条件 if (data.length >1){ /** * 1. 拆分两半 */ int[] firstHalf = new int[data.length/2]; System.arraycopy(data,0,firstHalf,0,firstHalf.length); mergeSort(firstHalf); int[] secondHalf = new int[data.length - data.length/2]; System.arraycopy(data,data.length/2,secondHalf,0,secondHalf.length); mergeSort(secondHalf); /** * 2. 合并两个部分 */ int[] temp = merge(firstHalf, secondHalf); /** * 重要：copy回原来的数组 */ System.arraycopy(temp, 0 , data, 0 , temp.length); } } ///合并 private static int[] merge(int[] a, int[] b) { int[] temp = new int[a.length+ b.length]; int i = 0; int j = 0; int k = 0; while(i<a.length && j<b.length){ if (a[i] <b[j]){ temp[k++]= a[i++]; }else{ temp[k++] = b[j++]; } } while(i < a.length) temp[k++] = a[i++]; while(j < b.length) temp[k++] = b[j++]; return temp; }
冒泡排序（BubbleSort）
- 思路：从后往前移动小元素，把小的元素移到大的元素前面，一次遍历至少可以移动一个小元素上去顶端。相邻元素之间的比较和交换，第一遍：从len-1 到0， 第二遍：从len-1 到1 ，……
- 平均/最差时间复杂度：O(n平方)
- 最好时间复杂度：O(n)【从arr[len-1] 到arr[0] 的过程没有一次交换】
- 稳定性：稳定
- Java写法：
/** * 冒泡排序 * 相邻元素比较和交换的过程 * 1. 从len-1 到 0 * 2. 从len-1 到 1 * 3. 从len-1 到 2 * ………… */ private static void bubbleSort(int[] data) { if (data== null|| data.length==0){ throw new RuntimeException("参数无效"); } for (int i=0;i<data.length-1;i++){ boolean isSwap = false; for(int j=data.length-1;j>i;j--){ if (data[j] < data[j-1]){ //交换 int temp = data[j-1]; data[j-1] =data[j]; data[j] = temp; ///设置为“需要交换” isSwap = true; } } if (!isSwap) return; } }
直接选择排序（SelectSort）
- 思路：每次从前往后查找，选择乱序中最小的元素，放到上面来。
- 时间复杂度：O(n平方)【只适用于从大量元素中选择一部分排序元素，例如从1w个元素中找出前10个元素】
- 稳定性：不稳定
- Java写法：
public static void selectSort(int[] data){ if (data == null || data.length <= 0) throw new RuntimeException("Invalid Paramemers"); ////每次从前到后选择最小的元素，把它交换上来 for(int i=0;i<data.length-1;i++){ int minIndex = i; for(int j = i+1;j<data.length;j++){ if (data[j] < data[minIndex]){ minIndex = j; } } if (minIndex != i) { //交换 int temp = data[minIndex]; data[minIndex] =data[i]; data[i] = temp; } } }
堆排序（HeapSort）
- 思路：一种树形选择排序算法。排序过程中将data[1…n]当做一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 分析：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
- Java写法：
/** * 堆排 * @param data */ public static void heapSort(int[] data, int len){ if(data==null || len<=0) throw new RuntimeException("invalid parameters"); /** * 1. 初始化堆（从最小个的堆开始整理，慢慢整理到最大个的堆） */ for(int i=len/2;i>=1;i--){//从最后一个拥有子结点的结点开始往上循环调整堆 initHeap(data, i,len); } System.out.println(data[1]); /** * 2. 一个个堆顶的值的输出，并重新调整堆的过程 */ for(int i=len;i>=2;i--){ //首先，将堆顶元素与数组末尾的元素换位置，然后，数组整理堆调整长度-1 int temp = data[i]; data[i] = data[1]; data[1] = temp; System.out.println("这次换位之后，末尾的值是："+ data[i]); initHeap(data, 1,i-1); } } //构造大顶堆的过程 private static void initHeap(int[] data, int low, int high) { int i = low; int j = i*2; int temp = data[i]; while(j<=high){ if (j<high && data[j]<data[j+1]) j++; if (temp < data[j]){ data[i] = data[j]; i = j; j = 2*i; }else break; } data[i] = temp;//从后往前赋值 }
直接插入排序（InsertSort）
- 思路：将数组中第二个元素开始，每个元素都慢慢往前查找最适合插入的点，然后插入（让前面的元素一一后移一位，让出位置给其插入。
- 平均/最差时间复杂度：O(n平方)
- 最好事件复杂度：O(n)
- 空间复杂度：O(1)
- 稳定性：稳定
- Java写法：
private static int[] insertSort(int[] data, int len) { if(data != null && len > 0) { for(int i = 1; i < len; ++i) { ///从第二个元素开始 int temp = data[i]; int j; for(j = i - 1; j >= 0 && data[j] >= temp; --j) { ///寻找适合的插入位置 data[j + 1] = data[j];///慢慢让前面的元素后移，腾出位置 } data[j + 1] = temp; ///最后插入 } return data; ///最终输出排好序的数组 }else { throw new RuntimeException("参数无效"); } }
希尔排序（ShellSort）
-
思路：用一个间隔参数（也可以说是增量）d， 去将原来插入排序的一一后移 1 步，变成 一一后移 d 步，比如：d = 2，那么，整个数组拆分成两组：{a[0],a[2],a[4]}和{a[1],a[3],a[5]}，然后组内比较，实际上就是间隔着去移位和插入【实际上，如果数组一开始就是有序的，那么Shell和Insert两种排序所需要的比较次数和移动次数都会很少。】
- n 比较小：InsertSort的最好和最坏时间复杂度O(n)和O(n平方)差别不大
- n 比较大：InsertSort的最坏事件复杂度则效率较低，而这时，由于一个d的存在，首先就把一部分本来需要的插入移位操作给做了，所以，这时，当gap以除以2的速度减小时，这一整趟排序整体需要的比较次数和移位次数就少了，于是效率高了。
平均时间复杂度：O(n^1.3)
空间复杂度：O(1)
稳定性：不稳定（因为每次‘分组’之后，原来排在前面的‘1’，可能变成排到后面去了）
-
Java写法：
private static int[] shellSort(int[] data, int len) { int d = len/2; while(d > 0){ for(int i=d; i< len; i++){ int temp = data[i];//取第len/2个元素（数组后半段）拿这个元素和前一组的所有元素进行比较，看到适当的位置就插入 int j = i - d; while(j >=0 && temp < data[j]){///每次需要腾出位置时，不是移动一个位置，而是移动d个位置 data[j+d] = data[j]; j -=d; } data[j+d] = temp; } d /=2; } return data; }
基数排序（RadixSort）
- 思路：将数组中每一个元素按：个位、十位、百位、……的顺序取一个自然数出来，然后对他们进行比较和排序。在排序过程中类似于HashMap的那种数组加链表的结构，所以需要一个辅助类Node，表示一个链表结点，只是这个数组只有0~9这几个元素。
- 平均/最好/最差时间复杂度：O(nlog(r)m)【r表示采用的基数，m表示堆数】
- 空间复杂度：O(r)
- 稳定性：稳定
- Java写法：
/** * 基数排序（桶排序），某些时候，效率会高一点 * 效率与：进制 、位数 、数组元素个数 、元素的最高位数 有关 */ private static int[] radixSort(int[] data, int len, int jinzhi, int weishu) { if (data == null || len <= 0 || jinzhi <= 0 || weishu < 1) throw new RuntimeException("Invalid Parameters"); ///这里就需要将这个数组中所有元素都变成一个Node类 class Node { int num; Node next; } Node myHead = new Node(); myHead.next = null; Node myTail = myHead; ///数组 转 链表 for (int i = 0; i < len; i++) { Node item = new Node(); item.num = data[i]; item.next = null; myTail.next = item; myTail = item; } ///=========================================== Node[] heads = new Node[jinzhi]; Node[] tails = new Node[jinzhi]; Node tempHead = null; for (int i = 0; i < weishu; i++) { /** * 1. 首先，初始化大数组 */ for (int j = 0; j < jinzhi; j++) { heads[j] = null; tails[j] = null; } tempHead = myHead; /** * 2. 然后，放桶 */ while (tempHead.next != null) {//证明有数组 tempHead = tempHead.next; int k = getDigit(tempHead.num, i); if (heads[k] == null) {///直接数组头就开始存放元素，这样就少了(进制)个Node空间 heads[k] = tempHead; tails[k] = heads[k]; } else { tails[k].next = tempHead; tails[k] = tails[k].next; } } /** * 3. 重新 连成链表 */ myHead.next = null; myTail = myHead; ///注意，取出每一个小链表来构建大链表的过程中： for (int j = 0; j < jinzhi; j++) { if (heads[j] !=null){ if (myHead.next == null){ myHead.next = heads[j]; }else{ //注意这里，当大链表不为空的情况，记得修复好myTail.next去连接 myTail.next = heads[j]; } myTail = tails[j]; } } myTail.next = null; tempHead = null; } /** * 4. 最终，重新：链表 转 数组 */ myTail = myHead; int k = 0; while (myTail.next != null) { myTail = myTail.next; data[k++] = myTail.num; } //返回数组 return data; } public static int getDigit(int x, int d) { int a[] = {1, 10, 100, 1000, 10000}; // 如果实例的最大数是百位数，那就只要到100就可以了 return ((x / a[d]) % 10); }
三、查找
二分查找
- 平均/最差时间复杂度：O(logn)
- 平均查找长度ASL：log(n+1) - 1
- 空间复杂度：O(1)
- 前提要求：线性表是有序的。
- 适用情况：为保持顺序表的有序，表的插入和删除操作都需要移动大量元素，所以折半查找特别适用于一旦建立就很少改动，又经常需要进行查找的线性表。
- Java写法：
public static int BinarySearch(int[] data, int len, int key){ if (data == null || len <=0) throw new RuntimeException("invalid parameters"); int low = 0; int high = len -1; while(low <= high){ int mid = (low + high)/2; if(data[mid] == key) return mid; else if (data[mid]< key) low = mid+1; else high = mid-1; } return -1; }
四、内排序方法的比较和总结
补充说明：
关于基数排序的平均时间复杂度、最差时间复杂度和空间复杂度，可以如下理解：
- 排序分类（按时间复杂度）：
- 平方阶O(n^2)排序，一般称为简单排序，例如直接插入排序，直接选择排序和冒泡排序
- 线性对数阶O(nlogn)排序，如快速排序、堆排序和归并排序
- 线性阶O(n)排序，如基数排序（假定数据的位数d和进制r为常量时）
- 使用结论
- 若n较小（如n<=50），可采用直接插入排序或直接选择排序。当元素规模较小时，直接插入排序较好；否则因为直接选择排序移动的元素少于直接插入排序，应选直接选择排序。
- 若文件初始状态基本有序（指正序），则应选用直接插入、冒泡或随机的快速排序。
- 若n较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序中较好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短；但堆排序所需的辅助空间比快速排序少，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的，若要求稳定，则可选用归并排序。
- 若要将两个有序表合并成一个新的有序表，最好的方法是归并排序。
- 在基于比较的排序方法中，至少是需要O(nlogn)的时间。而基数排序只需要一步就会引起r种可能的转移，即把一个元素装入r个队列之一，因此一般情况下，基数排序可能在O(n)时间内完成对n个元素的排序。但遗憾的是，基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合（例如实数型关键字）时，无法使用基数排序，这时只有借助于“比较”的方法来排序。由此可知，若n很大，元素的关键字位数较少且可以分解时，采用基数排序较好。
