冒泡排序 Bubble Sort
void doBubbleSort(int[] src) {
int len = src.length;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
int temp;
if (src[i] > src[j]) {
temp = src[j];
src[j] = src[i];
src[i] = temp;
}
}
printResult(i, src);
}
}
选择排序 Selection Sort
选择排序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。
选择排序与冒泡排序的区别在：冒泡排序每次比较后，如果发现顺序不对立即进行交换，而选择排序不立即进行交换，而是找出最小的元素后再进行交换。
void doChooseSort(int[] src) {
int len = src.length;
int temp;
for (int i = 0; i < len; i++) {
temp = src[i];
int j;
int samllestLocation = i;// 最小数的下标
for (j = i + 1; j < len; j++) {
if (src[j] < temp) {
temp = src[j];// 取出最小值
samllestLocation = j;// 取出最小值所在下标
}
}
src[samllestLocation] = src[i];
src[i] = temp;
printResult(i, src);
}
}
插入排序 Insertion Sort
简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序，折半插入排序留到“查找”内容中进行。
void doInsertSort2(int[] src) {
int len = src.length;
for (int i = 1; i < len; i++) {
int j;
int temp = src[i];
for (j = i; j > 0; j--) {
if (src[j - 1] > temp) {
src[j] = src[j - 1];
} else
// 如果当前的数，不小前面的数，那就说明不小于前面所有的数，
// 因为前面已经是排好了序的，所以直接通出当前一轮的比较
break;
}
src[j] = temp;
printResult(i, src);
}
}
快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
public class QuickSort {
public static int[] QuickSort0(int[] pData, int left, int right) {
int i = left, j = right;
int middle, strTemp;
middle = pData[(left + right) / 2];
do {
while ((pData[i] < middle) && (i < right))
i++;
while ((pData[j] > middle) && (j > left))
j--;
if (i <= j) {
strTemp = pData[i];
pData[i] = pData[j];
pData[j] = strTemp;
i++;
j--;
}
} while (i <= j);
for (int t = 0; t < pData.length; t++)
System.out.print(pData[t] + " ");
System.out.println("");
if (left < j) {
QuickSort0(pData, left, j);
}
if (right > i)
QuickSort0(pData, i, right);
return pData;
}
public static void main(String[] argv) {
int[] pData = { 1, 84, 85, 67, 600, 88, 999 };
QuickSort0(pData, 0, pData.length - 1);
}
}
// 归并排序中的合并算法
void Merge(int array[], int start, int mid, int end)
{
int temp1[10], temp2[10];
int n1, n2;
n1 = mid - start + 1;
n2 = end - mid;
// 拷贝前半部分数组
for (int i = 0; i < n1; i++)
{
temp1[i] = array[start + i];
}
// 拷贝后半部分数组
for (int i = 0; i < n2; i++)
{
temp2[i] = array[mid + i + 1];
}
// 把后面的元素设置的很大
temp1[n1] = temp2[n2] = 1000;
// 逐个扫描两部分数组然后放到相应的位置去
for (int k = start, i = 0, j = 0; k <= end; k++)
{
if (temp1[i] <= temp2[j])
{
array[k] = temp1[i];
i++;
}
else
{
array[k] = temp2[j];
j++;
}
}
}
// 归并排序
void MergeSort(int array[], int start, int end)
{
if (start < end)
{
int i;
i = (end + start) / 2;
// 对前半部分进行排序
MergeSort(array, start, i);
// 对后半部分进行排序
MergeSort(array, i + 1, end);
// 合并前后两部分
Merge(array, start, i, end);
}
}
名称 复杂度 说明 备注
冒泡排序
Bubble Sort O(N*N)
将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮
插入排序
Insertion sort
O(N*N)
逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置
起初，已经排序的元素序列为空
选择排序
O(N*N)
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。
快速排序
Quick Sort
O(n *log2(n))
先选择中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（递归）。
堆排序Heap Sort
O(n *log2(n))
利用堆（heaps）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。 近似完全二叉树
希尔排序
SHELL
O(n1+￡)
0<￡<1
选择一个步长(Step) ,然后按间隔为步长的单元进行排序.递归,步长逐渐变小,直至为1.
箱排序
Bin Sort
O(n)
设置若干个箱子，把关键字等于 k 的记录全都装入到第 k 个箱子里 ( 分配 ) ，然后按序号依次将各非空的箱子首尾连接起来 ( 收集 ) 。
分配排序的一种：通过 " 分配 " 和 "收集 " 过程来实现排序。
桶排序
Bucket Sort
O(n)
桶排序的思想是把 [0 ， 1) 划分为 n 个大小相同的子区间，每一子区间是一个桶。
public void binarySearch(int i, int[] arr, int left, int right) {
int mid = (left + right) / 2;
if (arr[mid] == i) {
System.out.println(i + " in " + mid);
return;
}
if (arr[mid] > i)
this.binarySearch(i, arr, left, mid-1);
if (arr[mid] < i) {
this.binarySearch(i, arr, mid+1 , right);
}
}
// 快速排序
public void quickSort(int[] arr, int l, int r) {
int left = l, right = r;
int middle = (left + right) / 2;
int midValue = arr[middle];
int temp;
do {
while (arr[left] < midValue && left < r)
// 如果排序正确，就++ 他没问题，放过去！
left++; // 他不对！等着挨揍！
while (arr[right] > midValue && right > l)
// 如果排序正确，就-- 他没问题，放过去！
right--;
if (left <= right) {
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
} while (left <= right);
printArray("快速排序: ", arr);
if (l < right) {
quickSort(arr, l, right);
}
if (left < r) {
quickSort(arr, left, r);
}
// printArray("快速排序: ", arr);
}
// 插入排序的平均时间复杂度也是O(n^2).
public int[] doInsertSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int temp = arr[i];
int j;
for (j = i; j > 0; j--) {
if (arr[j - 1] > temp) {
arr[j] = arr[j - 1];
} else {
break;
}
}
arr[j] = temp;
}
printArray("插入排序：", arr);
return arr;
}
// 选择排序，与冒泡排序的区别在于：在冒泡排序中，只要发现有比我小的，马上就进行交换。但是，在选择排序中，是最后才交换。
// 时间复杂度:O(n的平方)
public void doChooseSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len; i++) {
int minIndex = i;
int minValue = arr[i];
int j;
for (j = i + 1; j < len; j++) {
if (arr[i] > arr[j]) {
minValue = arr[j];
minIndex = j;
}
}
arr[minIndex] = arr[i];
arr[i] = minValue;
}
printArray("选择排序：", arr);
}
// 冒泡排序,时间复杂度：O(n的平方)
public void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len; i++) {
int temp;
for (int j = i + 1; j < len; j++) {
if (arr[i] > arr[j]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
printArray("冒泡排序：", arr);
}
|
收藏
淘帖
踩
