目录
分类
这里的排序可以分为两大类,
- 基于比较的排序
- 非基于比较的排序
其中有七种基于比较的排序:
- 直接插入排序
- 希尔排序
- 选择排序
- 堆排序
- 冒泡排序
- 快速排序
- 归并排序
一种非基于比较的排序:计数排序。
下面会通过Java来实现这八种排序,快速排序 和 归并排序 会有递归和非递归的实现。
直接插入排序
思路:
- 以两个for循环, 来实现两个数及两数中小数与前面数进行比较
- 假设第一个数为tmp,认为第一个数已经是排好序的,然后去和后面一个数进行比较
- 如果 j位置 的数 > j+1位置的数,把 j位置的数 赋值给 j+1位置;如果否,则向 j位置的前面去做,直到 j >= 0
- 重复进行步骤3,直到不符合循环条件
动图如下:
代码 :
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= 0; j--) {
if(array[j] > tmp){
array[j+1] = array[j];
}else{
array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:稳定
注意:
- 本身是一个稳定的排序,那么可以实现为不稳定的 。但是 如果一个排序 本身就是不稳定,那就不能实现稳定的排序。
- 数据越有序,直接插入排序越快
希尔排序
步骤:
希尔排序算是对直接排序进行优化,把其中的数据通过分组来不断简化 其中的有序性,上面有提到数据越有序,直接插入排序越快,不过这个分组并不是常规理解的那种把几个临近的数字化为一个组,而是,如下图所示:
通过间隔(gap)来实现分组,以上面 紫色的原图 为例,这时的gap为5,这代表着隔着5个空格的数为一组,然后进行组内排序,不断缩小间隔,增加每组内元素个数,再次进一步比较。
动图如下:
代码:
通过代码部分,我们也能看出这里面有直接排序的存在,只不过其中的部分和希尔排序有些出入。
public static void shellInsert(int[] array){
int gap = array.length;
while(gap > 1){
gap /= 2;
shell(array, gap);
}
}
private static void shell(int[] array, int gap) {
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i-gap;
for (; j >= 0; j-= gap) {
if(array[j] > tmp){
array[j+gap] = array[j];
}else{
array[j+gap] = tmp;
break;
}
}
array[j+gap] = tmp;
}
}
时间复杂度:O(N^1.2) - O(N^1.3)
空间复杂度:O(1)
稳定性:不稳定
选择排序
第一种思路
步骤:
- 选择排序,从名字上我们可以理解为从中不断选择出最小值,然后把它交换、排到前面
- 之所以说是不断选出最小值,是因为每次选出最小值都是以 i位置为准,而i位置也会不断变化,两个for循环来实现
动图如下:
代码:
public static void selectSort(int[] array){
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i+1; j < array.length; j++) {
if(array[j] < array[minIndex]){
minIndex = j;
}
}
swap(array,i,minIndex);
}
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
因为其中有元素位置的交换,所以我们可以自己写一个元素位置交换的方法。
时间复杂度:O(N^2) 和数据 是否有序无关
空间复杂度:O(1)
稳定性:不稳定
第二种思路
步骤:
这里主要是通过双指针的方法来找到 最小值 和 最大值的位置,当然,这是相对于每次i位置的数的大小。整体过程和上面一种思路有些相似的部分,相对来说,掌握两种方法还是要好一点。
public static void selectSort1(int[] array){
int left = 0;
int right = array.length-1;
while(left < right){
int minIndex = left;
int maxIndex = left;
for (int i = left+1; i <= right; i++) {
if(array[i] < array[minIndex]){
minIndex = i;
}
if(array[i] > array[maxIndex]){
maxIndex = i;
}
}
swap(array, left, minIndex);
//确保最大值的位置,最大值正好是 left 下标
//此时把最大值换到了minIndex下标
if(maxIndex == 0){
maxIndex = minIndex;
}
swap(array, right, maxIndex);
left++;
right--;
}
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
堆排序
步骤:
- 通过向下调整,创建一棵大根堆的树
- 通过把根节点和最后一个分支节点进行交换
- 再进行向下调整,完成排序
这个思路主要是通过大根堆的由大到小的原理,再通过换位来实现排序。
代码:
public static void heapSort(int[] array){
createHeap(array);
int end = array.length-1;
while(end > 0){
swap(array, 0 ,end);
siftDown(array, 0,end);
end--;
}
}
//创建大根堆
public static void createHeap(int[] array){
//length-1为最后一棵子树,-1 / 2 是为了找到最后一棵子树的根节点
for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
siftDown(array,parent,array.length);//向下调整,创建大根堆
}
}
/**
*
* @param array
* @param parent 每棵子树调整的根节点
* @param length 每棵子树调整的结束节点,跳到最后
*/
public static void siftDown(int[] array, int parent, int length) {
int child = 2*parent+1;
while(child < length){
if(child + 1 < length && array[child] < array[child +1]){
child++;
}
if(array[child] > array[parent]){
swap(array, child, parent);
parent = child;
child = 2*parent+1;
}else{
break;
}
}
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
时间复杂度:O(N*logN)
空间复杂度:O(1)稳定性:不稳定
冒泡排序
步骤:
通过相邻的两个元素相互比较,若 前位置 比 后位置的数要大,进行交换
动图如下:
下面代码部分是优化后的部分,未优化则不包含(flg元素 和 -i操作 )
代码:
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length-1; i++) {
boolean flg = false;
for (int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]){
swap(array, j, j+1);
flg = true;
}
}
//优化后的情况
//n个数据,比较n-1次,有可能其中i次就有序了
if(!flg){
break;
}
}
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
时间复杂度:不优化的情况(没有下方的boolean元素和-i操作) O(n^2)
优化以后,最快情况能达到O(N)
空间复杂度:O(1)
稳定性:稳定
快速排序
快速排序有三种方式能来实现
- 挖坑法
- hoare法
- 双指针法
如果问题问到快速排序,优先使用挖坑法,其次hoare法、双指针法
挖坑法
步骤:
- 先是实现 保证一个数的左边都比它小,右边都比它大,具体步骤如下步骤2,3,4
- 把第一个数存起来,为tmp,第一个位置当作是坑
- 从后面找比tmp小的值,放到坑里面,后面被放入坑的数的位置再当作坑
- 从前面找比tmp大的值,放到坑里面,前面被放入坑的数的位置当作坑
- 再向两边进行递归来处理
动图如下:
代码:
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是为了应对没有右边的情况,递归结束条件
if(start >= end){
return;
}
//整个方法走完之后,为第一次交换位置
int pivot = partition1(array, start, end);
quick(array, start, pivot-1);
quick(array, pivot+1, end);
}
private static int partition1(int[] array, int left, int right) {
int tmp = array[left];
while(left < right){
//循环找,不循环时则代表找到,找到比tmp小的数
while(left < right && array[right] >= tmp){
right--;
}
//挖坑法,然后填坑
//先是把第一个位置当作空,从后面数,如果有数比它小,就放到第一位
//然后是从前数,找最大值,找到后放到,刚刚的位置
//最后再把第一个数放到right和left相交的位置
//方法就是把两边的数分大小放到第一个数两边
array[left] = array[right];
//找到比tmp大的数
while(left < right && array[left] <= tmp){
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}
hoare法
步骤:
- 先是实现 保证一个数的左边都比它小,右边都比它大,具体步骤如下步骤2,3,4
- 把第一个数存起来,为tmp
- tmp和后面的数进行比较,然后把小数放到tmp前面,大数放到tmp后面
- 递归实现对tmp两边进行排序
代码如下:
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是为了应对没有右边的情况,递归结束条件
if(start >= end){
return;
}
//整个方法走完之后,为第一次交换位置
int pivot = partition(array, start, end);
quick(array, start, pivot-1);
quick(array, pivot+1, end);
}
private static int partition(int[] array, int left, int right) {
int tmp = array[left];
int tmpleft = left;
while(left < right){
//循环找,不循环时则代表找到
//right是为了把右边的小数移到左边
while(left < right && array[right] >= tmp){
right--;
}
while(left < right && array[left] <= tmp){
left++;
}
swap(array, left, right);
}
//因为left所找的是把左边的大数放到右边,所以找到最后的数会比left小,进行交换
swap(array,left,tmpleft);
return left;
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
双指针法
步骤:
这个主要是靠 cur + left 双指针来实现排序的,通过前后条件判断来进行排序
代码如下:
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是为了应对没有右边的情况,递归结束条件
if(start >= end){
return;
}
//整个方法走完之后,为第一次交换位置
int pivot = partition3(array, start, end);
quick(array, start, pivot-1);
quick(array, pivot+1, end);
}
public static int partition3(int[] array, int left, int right){
int prev = left;
int cur = left+1;
while(cur <= right){
if(array[left] > array[cur] && array[cur] != array[prev]){
swap(array, cur, prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
关于快速排序
时间复杂度:当数据给定的是1 2 3 4 5 6……有序的情况是 O(n^2)
最好的情况是O(N*logN)均匀分为叉,满二叉树
空间复杂度:最坏情况,递归是要开辟内存的O(N),最好的情况,满二叉树O(logN)
稳定性:不稳定
优化
通过上面三种方法,我们能看到三种方法中都有递归方式,每次递归都需要开辟内存,那么我们可以采取怎样的方式来减少递归的次数?
通过下面两种方法可以实现我们的想法:
三数取中
直接插入法【针对一定范围】
关于三数取中的意思是:找到左、右、中三个数的中位数。
部分直接插入,也可以减少递归次数,因为数据有越有序,直接插入法越快。
代码部分如下:
public class Sort {
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是为了应对没有右边的情况,递归结束条件
if(start >= end){
return;
}
if(end - start + 1 <= 7){
insertSortRange(array, start, end);
return;
}
int minIndex = getMiddleNum(array, start, end);
swap(array, start, minIndex);
//整个方法走完之后,为第一次交换位置
int pivot = partition1(array, start, end);
quick(array, start, pivot-1);
quick(array, pivot+1, end);
}
public static void insertSortRange(int[] array, int start, int end){
for (int i = start+1; i <= end; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= start; j--) {
if(array[j] > tmp){
array[j+1] = array[j];
}else{
array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
private static int getMiddleNum(int[] array, int left, int right){
int mid = (left+right)/2;
if(array[left] < array[right]){
if(array[mid] < array[left]){
return left;
}else if(array[mid] > array[right]){
return right;
}else{
return mid;
}
}else{
if(array[mid] > array[left]){
return left;
}else if(array[mid] < array[right]){
return right;
}else{
return mid;
}
}
}
private static int partition1(int[] array, int left, int right) {
int tmp = array[left];
while(left < right){
//循环找,不循环时则代表找到,找到比tmp小的数
while(left < right && array[right] >= tmp){
right--;
}
//挖坑法,然后填坑
//先是把第一个位置当作空,从后面数,如果有数比它小,就放到第一位
//然后是从前数,找最大值,找到后放到,刚刚的位置
//最后再把第一个数放到right和left相交的位置
//方法就是把两边的数分大小放到第一个数两边
array[left] = array[right];
//找到比tmp大的数
while(left < right && array[left] <= tmp){
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}
private static void swap(int[] array, int left, int right){
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
}
非递归实现
非递归实现,主要是栈的使用,通过控制出栈和入栈的元素及其顺序来实现
代码如下:
public static void quickSort(int[] array){
quickNor(array,0,array.length-1);
}
private static void quickNor(int[] array, int start, int end){
Deque<Integer> stack = new ArrayDeque<>();
int pivot = partition1(array, start, end);
//pivot左边有两个元素
if(pivot > start+1){
stack.push(start);
stack.push(pivot-1);
}
if(pivot < end-1){
stack.push(pivot+1);
stack.push(end);
}
while(!stack.isEmpty()){
end = stack.pop();
start = stack.pop();
pivot = partition1(array, start, end);
if(pivot > start+1){
stack.push(start);
stack.push(pivot-1);
}
if(pivot < end-1){
stack.push(pivot+1);
stack.push(end);
}
}
}
private static int partition1(int[] array, int left, int right) {
int tmp = array[left];
while(left < right){
//循环找,不循环时则代表找到,找到比tmp小的数
while(left < right && array[right] >= tmp){
right--;
}
//挖坑法,然后填坑
//先是把第一个位置当作空,从后面数,如果有数比它小,就放到第一位
//然后是从前数,找最大值,找到后放到,刚刚的位置
//最后再把第一个数放到right和left相交的位置
//方法就是把两边的数分大小放到第一个数两边
array[left] = array[right];
//找到比tmp大的数
while(left < right && array[left] <= tmp){
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}
private static void swap(int[] array, int left, int right){
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
归并排序
步骤:
- 先把要排序的元素分为两个组,接着继续向下分组(有种递归的味道了)
- 把每组元素比较完后,再把两个有序数组组合起来
代码如下:
public static void mergeSort(int[] array){
mergeSortTmp(array, 0, array.length-1);
}
//递归实现归并排序
private static void mergeSortTmp(int[] array, int left, int right) {
if(left >= right){
return;
}
//找中间值
int mid = (left + right)/2;
mergeSortTmp(array, left, mid-1);
mergeSortTmp(array, mid+1, right);
//走到这里,相当于全部分解完
//合并,合并有序数组
merge(array, left, mid, right);
}
private static void merge(int[] array, int left, int mid, int right) {
int[] tmp = new int[right-left+1];
int k = 0;
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
while(s1 <= e1 && s2 <= e2){
if(array[s1] <= array[s2]){
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while(s1 <= e1){
tmp[k++] = array[s1++];
}
while(s2 <= e2){
tmp[k++] = array[s2++];
}
//可以保证tmp数组是有序的
for (int i = 0; i < k; i++) {
array[i+left] = tmp[i];
}
}
时间复杂度:O(N*logN)
空间复杂度:O(N)
稳定性:稳定
非递归实现
非递归的实现,主要依靠的间隔gap的不断变大,然后通过每一小部分的排序进而来实现整个数据组的排序
代码如下:
public static void mergeSortNor(int[] array){
int gap =1;
while(gap < array.length){
for (int i = 0; i < array.length; i = i + gap*2) {
int left = i;
int mid = (left + gap -1);
if(mid >= array.length){
mid = array.length-1;
}
int right = mid + gap;
if(right >= array.length){
right = array.length-1;
}
merge(array, left, mid, right);
}
gap *= 2;
}
}
private static void merge(int[] array, int left, int mid, int right) {
int[] tmp = new int[right-left+1];
int k = 0;
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
while(s1 <= e1 && s2 <= e2){
if(array[s1] <= array[s2]){
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while(s1 <= e1){
tmp[k++] = array[s1++];
}
while(s2 <= e2){
tmp[k++] = array[s2++];
}
//可以保证tmp数组是有序的
for (int i = 0; i < k; i++) {
array[i+left] = tmp[i];
}
}
计数排序
非基于比较的排序
还有桶排序, 基数排序,感兴趣可以了解一下
使用场景:集中在某个范围内的一组数据
步骤:
- 根据数据的个数来创建数组
- 把对应元素出现的个数给到对应的位置,记录出现的次数
- 根据记录的次数,依次输出元素
代码如下 :
public static void countSort(int[] array){
//1.找最大值 和 最小值 来确定 计数数组的大小
int maxVal = array[0];
int minVal = array[0];
for (int i = 1; i < array.length; i++) {
if(array[i] > maxVal){
maxVal = array[i];
}
if(array[i] < minVal){
minVal = array[i];
}
}
int len = maxVal - minVal + 1;
int[] count = new int[len];
//2.遍历原来的数组array, 把每个元素 放到对应的计数数组中 进行比较
for (int i = 0; i < array.length; i++) {
int index = array[i];
count[index-minVal]++;
}
//3.依次 遍历计数数组
int index = 0;
for (int i = 0; i < count.length; i++) {
while(count[i] != 0){
array[index] = i+minVal;
index++;
count[i]--;
}
}
}
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » Java实现八种排序
发表评论 取消回复