1.冒泡排序：
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。
// 此段代码按照降序排列
int temp;
int size = a.length;
for(int i=1; i<size; i++) {
for(int j=0; j<size-i; j++) {
if(a[j] < a[j+1]) {
temp = a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
2.快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
public static void quickSort(int[] arr, int start, int end) {
if (end <= start) {
return;
}
int low = start;
int high = end;
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high]; // 将小于 pivot 的数放在地位
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low]; // 将大于 pivot 的数放在高位
}
arr[low] = pivot;
quickSort(arr, start, low - 1); // 递归排序左半部分
quickSort(arr, low + 1, end); // 递归排序右半部分
}
3.选择排序法
选择数组中的任意一个元素A，依次跟其他的元素X比较，若A>X，则交换，否则不交换。
//选择排序的优化
for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
int k = i;
for(int j = k + 1; j < arr.length; j++){// 选最小的记录
if(arr[j] < arr[k]){
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束，也就是找到本轮循环的最小的数以后，再与arr[i]进行交换
if(i != k){ //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
4.插入排序法
关键：在前面已经排好序的序列中找到合适的插入位置
步骤：
- 从第一个元素开始，该元素可以认为已经排好序。
- 取出下一个元素，在已经排好序的元素序列中从后往前扫描进行比较。
- 如果该元素(已排序) 大于新元素，则将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置后面。
- 重复步骤2~5
public int[] insertionSorting(int[] a) {
if (a == null) {
return a;
}
for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j--) {
if (a[j] < a[j - 1]) {
//交换数据
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
} else {
//此时插入的数据已经到达正确位置
break;
}
}
}
return a;
}
5.归并排序法
如果一个数组有n个数据，则可以把这个数组看作n个有序的子序列，每个子序列的长度为1，然后两两归并，就能得到[n/2]个长度为2（或者1，落单的)的字序列，再不断地两两归并，直到得到一个长度为n的有序数组。
public static void MergeSort2(int[] arr)
{
//使用非递归的方式来实现归并排序
int len = arr.length;
int k = 1;
while(k < len)
{
MergePass(arr, k, len);
k *= 2;
}
}
//MergePass方法负责将数组中的相邻的有k个元素的字序列进行归并
private static void MergePass(int[] arr, int k, int n)
{
int i = 0;
int j;
//从前往后,将2个长度为k的子序列合并为1个
while(i < n - 2*k + 1)
{
merge(arr, i, i + k-1, i + 2*k - 1);
i += 2*k;
}
//这段代码保证了，将那些“落单的”长度不足两两merge的部分和前面merge起来。
if(i < n - k )
{
merge(arr, i, i+k-1, n-1);
}
}
//merge函数实际上是将两个有序数组合并成一个有序数组
//因为数组有序，合并很简单，只要维护几个指针就可以了
private static void merge(int[] arr, int low, int mid, int high)
{
//temp数组用于暂存合并的结果
int[] temp = new int[high - low + 1];
//左半边的指针
int i = low;
//右半边的指针
int j = mid+1;
//合并后数组的指针
int k = 0;
//将记录由小到大地放进temp数组
for(; i <= mid && j <= high; k++)
{
if(arr[i] < arr[j])
temp[k] = arr[i++];
else
temp[k] = arr[j++];
}
//接下来两个while循环是为了将剩余的（比另一边多出来的个数）放到temp数组中
while(i <= mid)
temp[k++] = arr[i++];
while(j <= high)
temp[k++] = arr[j++];
//将temp数组中的元素写入到待排数组中
for(int l = 0; l < temp.length; l++)
arr[low + l] = temp[l];
}
网友评论