数据结构中的7种排序算法

时间复杂度主要考虑元素的移动次数。

结构如下：

1，定义：依次将待排序序列中的每一个记录插入到一个已经排好序的序列中，直到全部记录都排好序。

2，时间复杂度：在最好情况下，待排序序列为正序，时间复杂度为O(n)；最坏情况下，待排序序列为逆序，时间复杂度为O(n^2);平均情况下，时间复杂度为O(n^2)。

，空间复杂度：O(1)。

publicstaticvoidinsertSort(int[]nums){//直接插入排序for(inti=1;inums.length;i++){for(intj=i;j0;j--){if(nums[j]nums[j-1]){inttemp=nums[j];nums[j]=nums[j-1];nums[j-1]=temp;}}System.out.print(i+:);for(inta:nums)System.out.print(a+);System.out.println();}}

示例数组：{12,5,9,20,6,1,2}结果：

1，希尔排序是对直接插入排序的改进。

2，定义：先将整个待排序序列记录序列分割为若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

，时间复杂度：O（nlogn）~O(n^2)。

，空间复杂度：O(1).

publicstaticvoidshellSort(int[]nums){//希尔排序intd=nums.length/2;//增量大小while(d0){intk=0;//控制量while(kd){//进行直接插入排序for(inti=k;inums.length;i=i+d){for(intj=i;j0j-d=0;j=j-d){if(nums[j]nums[j-d]){inttemp=nums[j];nums[j]=nums[j-d];nums[j-d]=temp;}}}k++;//控制量增加}//whileSystem.out.print(d+:);for(inta:nums)System.out.print(a+);System.out.println();d=d/2;}//while}

示例数组：{12,5,9,20,6,1,2}结果：

1，定义：两两比较相邻记录的关键码，如果是反序则交换，直到没有反序的记录为止。

2，时间复杂度:在最好情况下，待排序序列为正序。其时间复杂度为O(n);在最坏情况下，待排序序列为逆序，时间复杂度为O(n^2)，平均时间复杂度为O(n^2).

，空间复杂度：O(1)。

publicstaticvoidbubbleSort(int[]nums){//冒泡排序for(inti=nums.length-1;i0;i--){for(intj=0;ji;j++){if(nums[j]nums[j+1]){inttemp=nums[j];nums[j]=nums[j+1];nums[j+1]=temp;}}System.out.print(nums.length-i+:);for(inta:nums)System.out.print(a+);System.out.println();}}

示例数组：{12,5,9,20,6,1,2}结果：

1，快速排序是对冒泡排序的改进。

2，定义：首先选一个轴值，将待排序记录分割成独立的两部分，左侧记录的关键字均小于或者等于轴值，右边记录的关键字均大于或者等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。

，在最好情况下，每次划分轴值的左侧子序列与右侧子序列的长度相同，时间复杂度为O(nlogn),在最坏情况下，待排序序列为正序或逆序，时间复杂度为O(n^2)；平均情况下，时间复杂度为O(nlogn)。

,空间复杂度：O(logn)。

publicstaticvoidquickSort(int[]nums,intlow,inthigh){//快速排序if(lowhigh){intdp=partition(nums,low,high);quickSort(nums,low,dp-1);quickSort(nums,dp+1,high);}else{return;}}publicstaticintpartition(int[]nums,intlow,inthigh){intpivot=nums[low];while(lowhigh){while(lowhighnums[high]=pivot)high--;nums[low]=nums[high];while(lowhighnums[low]=pivot)low++;nums[high]=nums[low];}nums[low]=pivot;//此时low等于high，所以，也可以写成nums[high]=pivot;returnlow;//此时low等于high，所以返回任意一个都是正确的}

示例数组：{12,5,9,20,6,1,2}结果：

1，定义：第i趟通过n-i次关键码的比较，在n-i-1(1=i=n-1)个记录中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。

2，时间复杂度：最好，最坏，平均的时间复杂度都是O(n^2)。

，空间复杂度：O(1)。

publicstaticvoidselectSort(int[]nums){//简单选择排序for(inti=0;inums.length-1;i++){intsIndex=i;//最小数下标intsNum=nums[i];//最小数大小for(intj=i+1;jnums.length;j++){if(nums[j]sNum){sIndex=j;sNum=nums[j];}}//交换inttemp=nums[i];nums[i]=nums[sIndex];nums[sIndex]=temp;System.out.print(i+1+:);for(inta:nums)System.out.print(a+);System.out.println();}}

示例数组：{12,5,9,20,6,1,2}结果：

1，堆排序是对简单选择排序的改进。

2，首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将他从堆中移走，并将剩下的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。

，时间复杂度：最好，最坏，平均的时间复杂度都是O(nlogn)。

，空间复杂度：O(nlogn)。

publicstaticvoidheapSort(int[]nums){//堆排序if(nums==null

nums.length=1){return;}buildMaxHeap(nums);//调用建立堆的函数//将堆顶元素调整至数组最后，然后，将当前堆继续调整为大顶堆for(inti=nums.length-1;i=1;i--){inttemp=nums[0];nums[0]=nums[i];nums[i]=temp;maxHeap(nums,i,0);System.out.print(nums.length-i+:);for(inta:nums)System.out.print(a+);System.out.println();}}privatestaticvoidbuildMaxHeap(int[]nums){//建立堆if(nums==null

nums.length=1){return;}inthalf=nums.length/2;for(inti=half;i=0;i--){maxHeap(nums,nums.length,i);}}privatestaticvoidmaxHeap(int[]nums,intheapSize,intindex){//递归调整为大顶堆intleft=index*2+1;intright=index*2+2;if(leftheapSizerightheapSize){//没有这个return，也是正确的，好吧!我没有看懂~return;}intlargest=index;if(leftheapSizenums[left]nums[index]){largest=left;}if(rightheapSizenums[right]nums[largest]){largest=right;}if(index!=largest){inttemp=nums[index];nums[index]=nums[largest];nums[largest]=temp;maxHeap(nums,heapSize,largest);}}

示例数组：{12,5,9,20,6,1,2}结果：代码参考链接

1，定义：将若干个有序序列进行两两归并，直至所有待排记录都在一个有序序列为止。

2，时间复杂度：最好，最坏，平均都是O(nlogn)。

，空间复杂度：O(n)。

publicstaticvoidmergeSort(int[]a,intleft,intright){if(leftright){//intcenter=(left+right)1;intcenter=(left+right)/2;mergeSort(a,left,center);mergeSort(a,center+1,right);merge(a,left,center,right);}else{return;}}publicstaticvoidmerge(int[]data,intleft,intcenter,intright){int[]tmpArr=newint[right+1];intmid=center+1;intindex=left;//index记录临时数组的索引inttmp=left;//从两个数组中取出最小的放入中临时数组while(left=centermid=right){tmpArr[index++]=(data[left]=data[mid])?data[left++]:data[mid++];}//剩余部分依次放入临时数组while(mid=right){tmpArr[index++]=data[mid++];}while(left=center){tmpArr[index++]=data[left++];}//将临时数组中的内容复制回原数组for(inti=tmp;i=right;i++){data[i]=tmpArr[i];}System.out.println(Arrays.toString(data));}publicstaticvoidmain(String[]args){int[]arr={12,5,9,20,6,1,2};mergeSort(arr,0,arr.length-1);}

示例数组：{12,5,9,20,6,1,2}结果：

转载请注明：http://www.92nongye.com/xxmb/204612463.html