小结
时间复杂度
所有的简单排序（时间复杂度为O（n的平方））的都是稳定排序，选择排序除外
所有的时间复杂度为O(nlogn)的都是不稳定排序，归并排序除外。
空间复杂度
归并排序的时间复杂度最高，为O（n），不过如果是原地归并的话貌似也就是O（1）
快速排序次之，为O(logn)
1，关于讲解可以参照这个系列的博客
http://blog.csdn.net/xiazdong/article/details/8462393
相关的pdf文档可以见云网盘
2，集中排序算法之间的性能比较
http://blog.csdn.net/deutschester/article/details/5946299
下面是几种排序方法的java实现：
其中涉及的相关辅助类有：
其实打印数组，不需要借助自己的辅助来，java.util中自带的标准类库中的Arrays.toString即可以实现这个功能。
package com.bobo.util; public class AssistUtil { /* * 该方法用于int型的数组打印 */ public static void displayArr(int[] array) { for (int i = 0; i < array.length; i++) { System.out.printf("%3s", array[i]); } System.out.println(); } public static void swap(int[] array, int i, int j) { // 这部判断很重要，否则在选择排序中碰到具有两个相同的元素的时候就可能出错 if (array[i] == array[j]) { return; } array[i] ^= array[j]; array[j] ^= array[i]; array[i] ^= array[j]; } }
一、冒泡排序
（1）长度为n的数组需要循环n-1次，第i次从0比较至倒数第i个元素，每次比较都是比较相邻的元素，每一轮最大的元素沉到底部，时间复杂度为O(n的平方)
（2）这种循环次数和边界有倒数关系的时候，一点编程上的技巧，利用--来控制循环
（3）另外两点对于冒泡排序的改进也值得关注
package com.bobo.util; public class BubbleSort { // 基本思想 // 比较相邻的两个元素，如果前面元素比后面元素大，那么进行交换 // 第i轮是从第1个元素进行比较，比较到倒数第i个元素 // 一共需要经过N-1轮 public static void bubbleSort(int[] array) { int maxIndex = array.length - 1; int i, j; for (i = 0; i <= maxIndex - 1; i++) { for (j = 1; j <= maxIndex - i; j++) { if (array[j - 1] > array[j]) { AssistUtil.swap(array, j, j - 1); } } } } // 逆序控制循环更一目了然 public static void bubbleSort1(int[] array) { int maxIndex = array.length - 1; int i, j; for (i = maxIndex; i >= 1; i--) { for (j = 0; j <= i - 1; j++) { if (array[j] > array[j + 1]) { AssistUtil.swap(array, j, j + 1); } } } } // 改进，如果某一轮没有发生交换，说明已经有序，排序已经完成 public static void bubbleSort2(int[] array) { int maxIndex = array.length - 1; boolean flag = true; for (int i = 0; i <= maxIndex - 1; i++) { flag = false; for (int j = 1; j <= maxIndex - i; j++) { if (array[j - 1] > array[j]) { AssistUtil.swap(array, j - 1, j); flag = true; } } if (flag == false) { break; } } } // 继续改进，如果100个数的数组，仅前面10个数无序，后面的数目都有序，并且都大于前面10个数，那么交换的位置一定《=10 // 记录下这个位置，那么只需要从头部遍历到这个位置即可 public static void bubbleSort3(int[] array) { int i, j; int maxIndex = array.length - 1; boolean flag = false; for (i = 0; i <= maxIndex - 1; i++) { flag = false; for (j = 1; j <= maxIndex - i; j++) { if (array[j - 1] > array[j]) { AssistUtil.swap(array, j - 1, j); flag = true; } } maxIndex = j; if (flag == false) { break; } } } }
二、选择排序
public static void selectSort(int[] array) { int maxIndex = array.length-1; for (int i = 0; i <= maxIndex - 1; i++) { int tempIndex = i; if (array[i] > array[i + 1]) { for (int j = i + 1; j<= maxIndex; j++) { if (array[tempIndex] > array[j]) { tempIndex = j; } } AssistUtil.swap(array, i, tempIndex); } } }
三、直接插入排序
package com.bobo.util; //直接插入排序 //在数组基本有序的时候，效率还是极高的 //基本思想，将数组分成0-i-1的有序部分，和i-n-1的无序部分 //每一次就是为i的元素在0-i-1中寻找合适的位置插入 public class InsertSort { public static void insertSort1(int[] array) { int i, j; int temp; int maxIndex = array.length - 1; for (i = 1; i <= maxIndex; i++) { temp = array[i]; if (array[i - 1] > array[i]) { for (j = i - 1; j >= 0 && array[j] > temp; j--) { array[j + 1] = array[j]; } array[j + 1] = temp; } } } // 如果利用交换来代替逐个后移，那么代码可以变换为 public static void insertSort2(int[] array) { int maxIndex = array.length - 1; int i, j; for (i = 1; i <= maxIndex; i++) { for (j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) { AssistUtil.swap(array, j, j+1); } } } }
四、希尔排序（本质可以看作分组的，步长为n的插入排序）
package com.bobo.util; //其实质就是分组插入排序，对于步长的选择，这里选择数组长度的一半 public class ShellSort { public static void shellSort(int[] array) { int length = array.length; int tag; int i, j, k; for (tag = length / 2; tag > 0; tag /= 2) { for (i = 0; i < tag; i++) { for (j = i + tag; j <= length - 1; j += tag) { if (array[j - tag] > array[j]) { for (k = j - tag; k >= 0 && array[k] > array[k + tag]; k -= tag) { AssistUtil.swap(array, k, k + tag); } } } } } } // 一种更简洁的方法是 public static void shellSort2(int[] array) { int length = array.length; int j, k; for (int tag = length / 2; tag > 0; tag /= 2) { for (j = tag; j <= length - 1; j++) { if (array[j - tag] > array[j]) { for (k = j - tag; k >= 0 && array[k] > array[k + tag]; k -= tag) { AssistUtil.swap(array, k, k + tag); } } } } } }
和分治法有关的两种排序算法：归并排序和快速排序
五、归并排序
package com.bobo.util; public class MergeSort { public static void mergeSort(int[] array, int[] targetArr, int start, int end) { int mid; if (start >= end) { return; } mid = (start + end) / 2; mergeSort(array, targetArr, start, mid); mergeSort(array, targetArr, mid + 1, end); mergeArray(array, targetArr, start, mid, end); } public static void mergeArray(int[] sourceArr, int[] targetArr, int start, int mid, int end) { int i = start, j = mid + 1, k = 0; while (i <= mid && j <= end) { if (sourceArr[i] <= sourceArr[j]) { targetArr[k++] = sourceArr[i++]; } else { targetArr[k++] = sourceArr[j++]; } } // 不知道为什么下面这种方法和上面的效果不同？ // for (i = start, j = mid + 1; i <= mid && j <= end; i++, j++) { // if (sourceArr[i] <= sourceArr[j]) { // targetArr[k++] = sourceArr[i]; // } else { // targetArr[k++] = sourceArr[j]; // } // } while (i <= mid) { targetArr[k++] = sourceArr[i++]; } while (j <= end) { targetArr[k++] = sourceArr[j++]; } for (i = 0; i < k; i++) { sourceArr[start + i] = targetArr[i]; } // System.out.println("start:" + start + ";mid:" + mid + ";end:" + end); // AssistUtil.displayArr(targetArr); // AssistUtil.displayArr(sourceArr); } }
六、快速排序
package com.bobo.util; public class QuickSort { // 快速排序的思想可以归纳为：挖坑填数，分治法 // 分区的过程，将比这个数目小的数移到数目的左边，将比该数大的数目移数目的右边 // 之后对左右重复这个过程 public static void quickSort(int[] array, int start, int end) { if (start >= end) { return; } int i = adjustArr(array, start, end); quickSort(array, start, i - 1); quickSort(array, i + 1, end); } // 调整数组，将比某个数小的移到其左边，大的移到右边 private static int adjustArr(int[] array, int start, int end) { int pivot = array[start]; int i = start, j = end; while (i < j) { while (i < j && array[j] >= pivot) { j--; } if (i < j) { array[i] = array[j]; i++; } while (i < j && array[i] <= pivot) { i++; } if (i < j) { array[j] = array[i]; j--; } } array[i] = pivot; return i; } }
七、堆排序
首先看java封装的堆的数据结构
package com.bobo.datastruct; import java.util.ArrayList; import java.util.Comparator; /** * 该类主要实现堆这种数据结构 分为最大堆和最小堆，根据c这个接口进行控制 * 堆的删除总是在第0个元素，然后调整至满足堆结构；插入总是在最后一个元素，然后调整至满足堆结构 * 第0个元素必定最大或者最小，每次取第0个元素和最后一个元素交换，然后调整堆结构，就可以实现堆排序（最大堆是从小到大，最小堆是从大到小） * * @author lixueyi x */ public class HeapStruct<T> { //利用比较接口来实现建立的堆是最大堆还是最小堆 private Comparator<? super T> c; private ArrayList<T> array; public HeapStruct(ArrayList<T> array, Comparator<? super T> c) { this.c = c; this.array = array; buildHeap(); } /** * 判断某个节点是否为叶子节点 * * @param pos * 节点在数组中对应的下标 * @return */ public boolean isLeaf(int pos) { return ((pos >= this.array.size() / 2) && (pos <= this.array.size() - 1)); } /** * 返回左孩子对应的下标2i+1 * * @param pos * @return */ public int leftChild(int pos) { return ((pos << 1) + 1); } /** * 返回右孩子对应的下标2i+2 * * @param pos * @return */ public int rightChild(int pos) { return (pos + 1) << 1; } /** * 获取堆的第0个元素（最大值或者最小值） * * @return */ public T getRoot() { return array.get(0); } public ArrayList<T> getArray() { return this.array; } /** * 向堆中插入一个元素 * * @param elem */ public void add(T elem) { // 方法一：如果是在头部增添元素，那么0之后的元素都符合堆的定义，仅需要从0下标调整一次既可 // array.add(0,elem); // adjustHeap(0,array.size()); // 不过，按照堆的定义，新元素只能被加入到最后的位置，重新buildHeap()自然也可以 // 不过由于新元素的父节点到根节点的序列必然有序，现在的任务类似于将这个新节点插入到这个有序区间中，因此类似于直接插入排序 // 下面是采用类似于直接插入的方式实现 array.add(elem); int maxIndex = array.size() - 1; // 方法一，新节点至根节点中的各级父节点调整一次 /* * for (int j = maxIndex, i = parent(maxIndex); i >= 0 && j != 0; j = i, * i = parent(j)) { System.out.println("i:" + i + ";j:" + j); if * (c.compare(array.get(i), array.get(j)) < 0) { swap(i, j); } } */ // 方法三：一次调整插入节点的各级父节点应当也可行，这和插入排序在本质上是一样的 // 注意0的父节点依旧是0，不能利用i>=0来控制循环，很容易陷入死循环 for (int i = parent(maxIndex); i > 0; i = parent(i)) { adjustHeap(i); } adjustHeap(0); } /** * 堆的删除，删除总是在下标为0处进行删除，然后用最后一个玄素来填充0的位置，从0开始做一次调整即可 */ public void delete() { swap(0, array.size() - 1); array.remove(array.size() - 1); adjustHeap(0); } /** * 返回父节点对应的下标 * * @param pos * @return */ public int parent(int pos) { return (pos - 1) >> 1; } private void buildHeap() { for (int i = array.size() / 2 - 1; i >= 0; i--) { adjustHeap(i); } } private void adjustHeap(int pos) { adjustHeap(pos, array.size()); } /** * 调整二叉树，使其满足堆的结构 * * @param pos * 调整的节点 * @param size * 调整堆的范围 */ private void adjustHeap(int pos, int size) { // System.out.println(pos); while (!isLeaf(pos)) { int l = leftChild(pos); int r = rightChild(pos); int next = pos; if (l < size && c.compare(array.get(l), array.get(pos)) > 0) { next = l; } if (r < size && c.compare(array.get(r), array.get(next)) > 0) { next = r; } if (next == pos) { // 这句话很重要，否则就可能成为死循环 return; } swap(pos, next); pos = next; // System.out.println(array); } } private void swap(int pos, int next) { if (c.compare(array.get(pos), array.get(next)) != 0) { T temp = array.get(pos); array.set(pos, array.get(next)); array.set(next, temp); } } public void sort() { int size = array.size(); /* * for(int i=0;i<size-1;i++){ swap(0,size-1-i); adjustHeap(0,size-i-1); * } */ for (int i = size - 1; i > 0; i--) { swap(0, i); // 此时只可能是第0个元素不符合堆的定义，因此调整是自上而下调整一次即可，不需要进行循环 adjustHeap(0, i); } } }
明白其实现后，根据下标为0的元素总是最大（最大堆），或者最小（最小堆）；将下标为0的元素和最后一个交换，调整，即可进行排序，详见上面代码的注释。
堆结构通常用来实现大数据中的topN，对上述结构稍作修改，就可以实现这个目的，同时还能够实现去重功能
package com.bobo.util; import java.util.ArrayList; import java.util.Comparator; import java.util.HashSet; /** * 该类主要实现堆这种数据结构 分为最大堆和最小堆，根据c这个接口进行控制 * 堆的删除总是在第0个元素，然后调整至满足堆结构；插入总是在最后一个元素，然后调整至满足堆结构 * 第0个元素必定最大或者最小，每次取第0个元素和最后一个元素交换，然后调整堆结构，就可以实现堆排序（最大堆是从小到大，最小堆是从大到小） * * @author lixueyi x */ public class HeapStruct<T> { // 利用比较接口来实现建立的堆是最大堆还是最小堆 private Comparator<? super T> c; private ArrayList<T> array; // 维持堆结构的大小, private int n; public HeapStruct(ArrayList<T> array, Comparator<? super T> c) { this.c = c; this.array = array; buildHeap(); } /** * 这个构造函数用来维持一个固定大小的堆，大小为n，该构造函数可以用于对大数据求取topN * * @param array * @param c * @param n */ public HeapStruct(ArrayList<T> array, Comparator<? super T> c, int n) { this.c = c; this.array = array; this.n = n; buildHeap(); } /** * 判断某个节点是否为叶子节点 * * @param pos * 节点在数组中对应的下标 * @return */ public boolean isLeaf(int pos) { return ((pos >= this.array.size() / 2) && (pos <= this.array.size() - 1)); } /** * 返回左孩子对应的下标2i+1 * * @param pos * @return */ public int leftChild(int pos) { return ((pos << 1) + 1); } /** * 返回右孩子对应的下标2i+2 * * @param pos * @return */ public int rightChild(int pos) { return (pos + 1) << 1; } /** * 获取堆的第0个元素（最大值或者最小值） * * @return */ public T getRoot() { return array.get(0); } public ArrayList<T> getArray() { return this.array; } /** * 向堆中插入一个元素 * * @param elem */ public void add(T elem) { // 方法一：如果是在头部增添元素，那么0之后的元素都符合堆的定义，仅需要从0下标调整一次既可 // array.add(0,elem); // adjustHeap(0,array.size()); // 不过，按照堆的定义，新元素只能被加入到最后的位置，重新buildHeap()自然也可以 // 不过由于新元素的父节点到根节点的序列必然有序，现在的任务类似于将这个新节点插入到这个有序区间中，因此类似于直接插入排序 // 下面是采用类似于直接插入的方式实现 array.add(elem); int maxIndex = array.size() - 1; // 方法一，新节点至根节点中的各级父节点调整一次 /* * for (int j = maxIndex, i = parent(maxIndex); i >= 0 && j != 0; j = i, * i = parent(j)) { System.out.println("i:" + i + ";j:" + j); if * (c.compare(array.get(i), array.get(j)) < 0) { swap(i, j); } } */ // 方法三：一次调整插入节点的各级父节点应当也可行，这和插入排序在本质上是一样的 // 注意0的父节点依旧是0，不能利用i>=0来控制循环，很容易陷入死循环 for (int i = parent(maxIndex); i > 0; i = parent(i)) { adjustHeap(i); } adjustHeap(0); } public void insert(T elem) { if (this.array.size() > 0 && c.compare(this.getRoot(), elem) < 0) { return; } // 如果需要去除重复，那么重写T对象的equals方法 for (int i = 0; i < array.size(); i++) { if (elem.equals(array.get(i))) { return; } } if (this.array.size() >= n) { this.delete(); this.add(elem); } else { this.add(elem); } } /** * 堆的删除，删除总是在下标为0处进行删除，然后用最后一个玄素来填充0的位置，从0开始做一次调整即可 */ public void delete() { swap(0, array.size() - 1); array.remove(array.size() - 1); adjustHeap(0); } /** * 返回父节点对应的下标 * * @param pos * @return */ public int parent(int pos) { return (pos - 1) >> 1; } private void buildHeap() { for (int i = array.size() / 2 - 1; i >= 0; i--) { adjustHeap(i); } } private void adjustHeap(int pos) { adjustHeap(pos, array.size()); } /** * 调整二叉树，使其满足堆的结构 * * @param pos * 调整的节点 * @param size * 调整堆的范围 */ private void adjustHeap(int pos, int size) { // System.out.println(pos); while (!isLeaf(pos)) { int l = leftChild(pos); int r = rightChild(pos); int next = pos; if (l < size && c.compare(array.get(l), array.get(pos)) > 0) { next = l; } if (r < size && c.compare(array.get(r), array.get(next)) > 0) { next = r; } if (next == pos) { // 这句话很重要，否则就可能成为死循环 return; } swap(pos, next); pos = next; // System.out.println(array); } } private void swap(int pos, int next) { if (c.compare(array.get(pos), array.get(next)) != 0) { T temp = array.get(pos); array.set(pos, array.get(next)); array.set(next, temp); } } public void sort() { int size = array.size(); /* * for(int i=0;i<size-1;i++){ swap(0,size-1-i); adjustHeap(0,size-i-1); * } */ for (int i = size - 1; i > 0; i--) { swap(0, i); // 此时只可能是第0个元素不符合堆的定义，因此调整是自上而下调整一次即可，不需要进行循环 adjustHeap(0, i); } } }
对上述topN的调用
package com.bobo.entity; import javax.swing.text.html.HTMLDocument.HTMLReader.IsindexAction; public class Tiezi { private String id; private String title; private String replyNums; private String createTime; private String keyWordId; public Tiezi(String id, String title, String replyNums, String createTime, String keyWordId) { this.id = id; this.title = title; this.replyNums = replyNums; this.createTime = createTime; this.keyWordId = keyWordId; } public String getId() { return id; } public void setId(String id) { this.id = id; } public String getTitle() { return title; } public void setTitle(String title) { this.title = title; } public String getReplyNums() { return replyNums; } public void setReplyNums(String replyNums) { this.replyNums = replyNums; } public String getCreateTime() { return createTime; } public void setCreateTime(String createTime) { this.createTime = createTime; } public String getKeyWordId() { return keyWordId; } public void setKeyWordId(String keyWordId) { this.keyWordId = keyWordId; } @Override public String toString() { return id + " " + title + " " + replyNums + " " + createTime + " " + keyWordId; } @Override public boolean equals(Object obj) { if (obj instanceof Tiezi) { return this.getId().equals(((Tiezi) obj).getId()); } return false; } }
package com.bobo.entity; import java.util.Comparator; import javax.swing.text.html.HTMLDocument.HTMLReader.IsindexAction; public class TieziComparator implements Comparator<Tiezi> { @Override public int compare(Tiezi o1, Tiezi o2) { return Integer.parseInt(o2.getReplyNums()) - Integer.parseInt(o1.getReplyNums()); } }
package com.bobo.datapre; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileWriter; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import com.bobo.entity.Tiezi; import com.bobo.entity.TieziComparator; import com.bobo.util.HeapStruct; public class TianyaDataPreByMyHeap { private static int TitleCount = 10; // 1,找到热议话题 // 2，找到关于导演的热议话题 // 3，找到对于主持人的热议话题 // 4，定位热门节目 // 5，定位热门演员 /** * @param args */ public static void main(String[] args) { // 事实上函数参数都是通过 String inPath = "./mydata/tieba.retain"; String outPath = "./mydata/topNtiezi.data"; TianyaDataPreByMyHeap tianyaDataPre = new TianyaDataPreByMyHeap(); long start = System.currentTimeMillis(); tianyaDataPre.getTopNTitleAboutKeyword(TitleCount, null, inPath, outPath); long end = System.currentTimeMillis(); System.out.println("系统花费时间：" + (end - start) / 1000); } /** * ��ú� * * @param n * @return */ public void getTopNTitleAboutKeyword(int n, String keywordId, String inPath, String outPath) { ArrayList<Tiezi> array = new ArrayList<Tiezi>(); TieziComparator c = new TieziComparator(); HeapStruct<Tiezi> tieziHeap = new HeapStruct<Tiezi>(array, c, n); FileInputStream fis = null; InputStreamReader isr = null; BufferedReader br = null; FileWriter fw = null; PrintWriter pw = null; try { fis = new FileInputStream(inPath); isr = new InputStreamReader(fis, "UTF8"); br = new BufferedReader(isr); fw = new FileWriter(outPath); pw = new PrintWriter(fw); String line = ""; while ((line = br.readLine()) != null) { String[] lineArr = line.trim().split(" "); String tieziId = lineArr[0]; String title = lineArr[1]; String replyNums = lineArr[2]; String createTime = lineArr[3]; String curKeywordId = lineArr[4]; // 如果不设定关键词或者过滤关于某个演员的关键词 if (keywordId == null || curKeywordId.equals(keywordId)) { tieziHeap.insert(new Tiezi(tieziId, title, replyNums, createTime, curKeywordId)); } } tieziHeap.sort(); for (int i = 0; i < array.size(); i++) { System.out.println(array.get(i).toString()); } } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } finally { try { br.close(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } pw.close(); } } }
如果利用c++实习
#ifndef MYHEAP_H #define MYHEAP_H #include<iostream> using namespace std; class MyHeap{ private: int* array; int len; public: int* getArray(){return array;} int getRoot(){return *array;} int getParentIndex(int i){return (i>>1)-1;} int getLeftIndex(int i){return (i<<1)+1;} int getRightIndex(int i){return (i<<1)+2;} bool isLeaf(int i){return i>=len/2&&i<=len-1;} MyHeap(int n); ~MyHeap(); void buildHeap(); void adjustDown(int pos); void adjustDown(int pos,int size); void adjustUp(int pos); void adjustUp(); void insert(int elem); void deleteRoot(); void sort(); void setArray(int *array, int n); void print(); void setElem(int pos , int elem); }; #endif
#include"my_heap.h" MyHeap::MyHeap(int n){ this->len=n; array=new int[n]; } MyHeap::~MyHeap(){ //delete[] array; } void swap(int &a ,int &b){ if(a==b){ return; } a^=b; b^=a; a^=b; } void MyHeap::adjustDown(int pos,int size){ int cur=pos; while(!isLeaf(cur)&&cur<size){ int left=getLeftIndex(cur); int right=getRightIndex(cur); int next=cur; if(left<size&&array[cur]<array[left]){ next=left; } if(right<size&&array[next]<array[right]){ next=right; } if(cur==next){ return; } swap(array[cur],array[next]); cur=next; } } void MyHeap::adjustDown(int pos){ this->adjustDown(pos,len); } void MyHeap::adjustUp(int pos){ for(int i=getParentIndex(pos),j=pos;i>=0&&array[i]<array[j];i=getParentIndex(i),j=getParentIndex(j)){ swap(array[i],array[j]); } } void MyHeap::adjustUp(){ this->adjustUp(len-1); } void MyHeap:: setElem(int pos,int elem){ this->array[pos]=elem; } void MyHeap::print(){ for(int i=0;i<len;i++){ cout<<array[i]<<" "; } cout<<endl; } void MyHeap::setArray(int *array,int n){ for(int i=0;i<n;i++){ this->array[i]=array[i]; } } void MyHeap::buildHeap(){ for(int i=(len>>1)-1;i>=0;i--){ adjustDown(i); } } void MyHeap::deleteRoot(){ //交换第一个和最后一个，进行一次调整 swap(array[0],array[len-1]); adjustDown(0,len-1); } void MyHeap::insert(int elem){ array[len-1]=elem; adjustUp(); } void MyHeap::sort(){ //每次都取出第一个 for(int i=len-1;i>0;i--){ cout<<array[0]<<" "; swap(array[0],array[i]); adjustDown(0,i); } cout<<array[0]<<" "; cout<<endl; }
八、计数排序
计数排序的事件复杂度为线性复杂度O(n),但是空间复杂度高，需要事先对于乱序数组的分布大概了解，还有两个尚未解决的问题、
遗留问题，如果原数组中存在两个相同的数字呢？
#include<cstring> #include<iostream> using namespace std; int main(){ int unSort[]={1,4,2,9,5,7}; void displayArr(int*,int); void countSort(int*,int,int,int); cout<<"排序之前的数组："<<endl; displayArr(unSort,6); countSort(unSort,9,1,6); cout<<"排序之后的数组："<<endl; displayArr(unSort,6); return 0; } void displayArr(int* arr,int n){ for(int i=0;i<n;i++){ cout<<arr[i]<<" "; } cout<<endl; } //采用计数排序方法 //其中unSort是待排序的数组 //max为数组中的最大值 //nlen为数组的长度 //潜在问题：如果最大值比数组长度大很多，或者有负数呢？ void countSort(int* unSort,int max,int min,int nlen){ int lenCount=max-min+1; int* pCount=new int[lenCount]; int index; for(int i=0;i<lenCount;i++){ pCount[i]=0; } for(int i=0;i<nlen;i++){ int index=unSort[i]-min; pCount[index]++; } cout<<"初步计数之后的数组："<<endl; displayArr(pCount,lenCount); for(int i=1;i<lenCount;i++){ pCount[i]+=pCount[i-1]; } cout<<"计数之后的数组："<<endl; displayArr(pCount,lenCount); int *pSort=new int[nlen]; for(int i=0;i<nlen;i++){ //讲数据放在指定的位置，对于数a，不大于数a的个数就是数a当处的位置 int index=unSort[i]-min; pSort[--pCount[index]]=unSort[i]; //要考虑可能存在相同的数 } for(int i=0;i<nlen;i++){ unSort[i]=pSort[i]; } delete[] pSort; delete[] pCount; }
九、在讲解子字符串包含的问题的时候发现一种bit排序的思想
其时间复杂度为O（n），控件复杂度为这n个数目中（（max-min）/8）；不过以上没有考虑重复元素，如果考虑重复元素，需要辅助数组，相对复杂
void setBit(char *p,int pos){ //计算放置在哪个char字节中,可以看出，大的数字是放置在较大索引的char数组元素中 for(int i=0;i<(pos/BYTESIZE);i++){ p++; } //计算在对应char字节的哪一位上，可以看出，大的元素防止在高位 *p=*p|(0x01<<(pos%BYTESIZE)); } //取出位上对应的元素值,bufferLen为采用的char数组的长度，pBuffer为采用的char数组首地址的指针 //由此可见，为某一位赋值的时候，方法是*p|(0x01<<pos) //取出某一位置是0还是1的时候，方法是*p&(0x01<<pos)==(0x01<<pos) void getBit(int bufferLen,char *pBuffer){ for(int i=0;i<bufferLen;i++){ for(int j=0;j<BYTESIZE;j++){ if((*pBuffer&(0x01<<j))==(0x01<<j)){ cout<<i*BYTESIZE+j<<" "; } } pBuffer++; } } //这还真是一种bit排序的思路，复杂度为O(n),空间复杂度为O（(max-min)/8） void bitmapSortDemo(){ int num[]={3,5,1,10}; //最大值为10，但是一个char字节能够放置的最大元素为8，因此需要两个字节 const int bufferLen=2; char *pBuffer=new char[2]; memset(pBuffer,0,bufferLen); for(int i=0;i<4;i++){ setBit(pBuffer,num[i]); } getBit(bufferLen,pBuffer); }