排序算法整理
2017-08-07 本文已影响0人
博客的博客
排序算法总览
排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。内排序有可以分为以下几类：
(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。
(2)、选择排序：简单选择排序、堆排序。
(3)、交换排序：冒泡排序、快速排序。
(4)、归并排序
(5)、线性时间排序：计数排序、基数排序、桶排序
算法杂度以及稳定性分析
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
排序算法整理.png
图片名词解释：
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
冒泡排序
public static void bubbleSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
for(int i=0; i<arr.length-1; i++) {
for(int j=arr.length-1; j>i; j--) {
if(arr[j] < arr[j-1]) {
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
选择排序
public static void selectSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
插入排序
public static void insertSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
for (int i = 1; i < arr.length; i++) {
int j = i;
int target = arr[i];
while (j > 0 && target < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = target;
}
}
快速排序
public static int partition(int[] arr, int left, int right) {
int pivotKey = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivotKey)
right--;
arr[left] = arr[right];
while (left < right && arr[left] <= pivotKey)
left++;
arr[right] = arr[left];
}
arr[left] = pivotKey;
return left;
}
public static void quickSort(int[] arr, int left, int right) {
if (left >= right)
return;
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos - 1);
quickSort(arr, pivotPos + 1, right);
}
public static void sort(int[] arr) {
if (arr == null || arr.length == 0)
return;
quickSort(arr, 0, arr.length - 1);
}
堆排序
public static void heapAdjust(int[] arr, int start, int end) {
int temp = arr[start];
for (int i = 2 * start + 1; i <= end; i *= 2) {
//左右孩子的节点分别为2*i+1,2*i+2
//选择出左右孩子较小的下标
if (i < end && arr[i] < arr[i + 1]) {
i++;
}
if (temp >= arr[i]) {
break; //已经为大顶堆，=保持稳定性。
}
arr[start] = arr[i]; //将子节点上移
start = i; //下一轮筛选
}
arr[start] = temp; //插入正确的位置
}
public static void heapSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
//建立大顶堆
for (int i = arr.length / 2; i >= 0; i--) {
heapAdjust(arr, i, arr.length - 1);
}
for (int i = arr.length - 1; i >= 0; i--) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
heapAdjust(arr, 0, i - 1);
}
}
希尔排序
public static void shellInsert(int[] arr, int d) {
for (int i = d; i < arr.length; i++) {
int j = i - d;
int temp = arr[i]; //记录要插入的数据
while (j >= 0 && arr[j] > temp) { //从后向前，找到比其小的数的位置
arr[j + d] = arr[j]; //向后挪动
j -= d;
}
if (j != i - d) //存在比其小的数
arr[j + d] = temp;
}
}
public static void shellSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
int d = arr.length / 2;
while (d >= 1) {
shellInsert(arr, d);
d /= 2;
}
}
归并排序
public static void mergeSort(int[] arr) {
mSort(arr, 0, arr.length - 1);
}
public static void mSort(int[] arr, int left, int right) {
if (left >= right)
return;
int mid = (left + right) / 2;
mSort(arr, left, mid); //递归排序左边
mSort(arr, mid + 1, right); //递归排序右边
merge(arr, left, mid, right); //合并
}
public static void merge(int[] arr, int left, int mid, int right) {
//[left, mid] [mid+1, right]
int[] temp = new int[right - left + 1]; //中间数组
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}
计数排序
public static void countSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
int max = max(arr);
int[] count = new int[max + 1];
Arrays.fill(count, 0);
for (int i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
int k = 0;
for (int i = 0; i <= max; i++) {
for (int j = 0; j < count[i]; j++) {
arr[k++] = i;
}
}
}
public static int max(int[] arr) {
int max = Integer.MIN_VALUE;
for (int ele : arr) {
if (ele > max)
max = ele;
}
return max;
}
桶排序
public static void bucketSort(int[] arr) {
if (arr == null && arr.length == 0)
return;
int bucketNums = 10; //这里默认为10，规定待排数[0,100)
List<List<Integer>> buckets = new ArrayList<List<Integer>>(); //桶的索引
for (int i = 0; i < 10; i++) {
buckets.add(new LinkedList<Integer>()); //用链表比较合适
}
for (int i = 0; i < arr.length; i++) {
buckets.get(f(arr[i])).add(arr[i]);
}
for (int i = 0; i < buckets.size(); i++) {
if (!buckets.get(i).isEmpty()) {
Collections.sort(buckets.get(i)); //对每个桶进行快排
}
}
int k = 0;
for (List<Integer> bucket : buckets) {
for (int ele : bucket) {
arr[k++] = ele;
}
}
}
public static int f(int x) {
return x / 10;
}
基数排序
public static void radixSort(int[] arr) {
if (arr == null && arr.length == 0)
return;
int maxBit = getMaxBit(arr);
for (int i = 1; i <= maxBit; i++) {
List<List<Integer>> buf = distribute(arr, i); //分配
collecte(arr, buf); //收集
}
}
public static List<List<Integer>> distribute(int[] arr, int iBit) {
List<List<Integer>> buf = new ArrayList<List<Integer>>();
for (int j = 0; j < 10; j++) {
buf.add(new LinkedList<Integer>());
}
for (int i = 0; i < arr.length; i++) {
buf.get(getNBit(arr[i], iBit)).add(arr[i]);
}
return buf;
}
public static void collecte(int[] arr, List<List<Integer>> buf) {
int k = 0;
for (List<Integer> bucket : buf) {
for (int ele : bucket) {
arr[k++] = ele;
}
}
}
public static int getMaxBit(int[] arr) {
int max = Integer.MIN_VALUE;
for (int ele : arr) {
int len = (ele + "").length();
if (len > max)
max = len;
}
return max;
}
public static int getNBit(int x, int n) {
String sx = x + "";
if (sx.length() < n)
return 0;
else
return sx.charAt(sx.length() - n) - '0';
}
参考文章
http://www.cnblogs.com/wxisme/p/5243631.html
http://blog.csdn.net/sunxianghuang/article/details/51872360
