排序算法相关知识点 _算法

一．插入排序插入排序的时间复杂度是O(n^2) 。
插入排序重复地将新元素插入到一个排好序的子线性表中，直到整个线性表排好序。
【排序算法相关知识点】算法描述如下：
for(int i=0;i<list.length;i++){将list[i]插入，将导致已排好序的子线性表后移。} public static void insertionSort(int[] list)
{
if(list.length>=2)
{
for(int i=1;i<list.length;i++)
{
int currentElement=list[i];
int k;
for(k=i-1;k>=0&&list[k]>currentElement;k--) {
list[k+1]=list[k];
}
list[k+1]=currentElement;
}
}
}二．冒泡排序最差情况下冒泡的时间复杂度是O(n^2) 。
冒泡排序多次遍历数组，在每次遍历中连续比较相邻的元素，如果没按顺序排列，就交换它们的值。
较小的值像“气泡”一样逐渐浮向顶部，而较大的值沉向底部。第一次遍历后最后一个元素是数组中的最大值，第二次遍历后，倒数第二个元素是数组中第二大的数。这个过程持续到所有元素都排好序。
public static void bubbleSort(int[] list)
{
boolean needNextPass=true;
for(int k=1;k<list.length&&needNextPass;k++) {
needNextPass=false;
for(int i=0;i<list.length-k;i++) {
if (list[i] > list[i + 1]) {
int temp = list[i + 1];
list[i + 1] = list[i];
list[i] = temp;
needNextPass=true;
}
}
}
System.out.println(Arrays.toString(list));
}三．归并排序归并排序的时间复杂度是O(nlogn) 。
归并排序将数组分为2半，对每部分递归地应用归并排序。在每部分排好序后对它们进行归并。

文章插图

public class MergeSort {
public static void mergeSort(int[] list)
{
if(list.length>1) {
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
merge(firstHalf, secondHalf, list);
}
}
public static void merge(int[] list1,int[] list2,int[] temp)
{
int current1=0;
int current2=0;
int current3=0;
while (current1<list1.length&&current2<list2.length) {
if(list1[current1]<list2[current2])
temp[current3++]=list1[current1++];
else
temp[current3++]=list2[current2++];
}
while (current1<list1.length) {
temp[current3++]=list1[current1++];
}
while (current2<list2.length) {
temp[current3++]=list2[current2++];
}
}
}四．快速排序快速排序的平均时间为O(nlogn) –各种精确的平均情况分析超出本笔记目标。快排的空间效率高于归并排序。
快速排序的工作机制：该算法在数组中选择一个元素称为主元(pivot)，并将数组分为两部分，使得前半部的元素都小于或等于主元，后半部的元素都大于主元。对第一部分递归地应用快速排序算法，然后对第二部分递归地应用快速排序算法。
快速排序由C.A.R.Hoare于1962年开发。主元的选择会影响算法的性能。

文章插图

文章插图

public class QuickSort {
public static void quickSort(int[] list)
{
quickSort(list,0,list.length-1);
}
public static void quickSort(int[] list,int first,int last)
{
if(last>first) {
int pivotIndex = partition(list, first, last);
quickSort(list, 0, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
}
}
public static int partition(int[] list,int first,int last)
{
int pivot=list[first];
int low=first+1;
int high=last;
while(high>low) {
while(low<=high&&list[low]<=pivot)
low++;
while(high>=low&&list[high]>=pivot)
high--;
if(high>low) {
int temp=list[high];
list[high]=list[low];
list[low]=temp;
}
} while(high>first&&list[high]>=pivot)
high--;
if(pivot>list[high]) {
list[first]=list[high];
list[high]=pivot;
return high;
}
else {
return first;
}
}
}五．堆排序堆排序的时间复杂度为O(nlogn)，与归并排序相同，但堆排序的空间效率高于归并排序。