数据结构与算法-选择&冒泡&快排&计数

这篇具有很好参考价值的文章主要介绍了数据结构与算法-选择&冒泡&快排&计数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

    一:选择排序

    场景:找出一个班上身高最高的人你会怎么找?A B C D A B

选择排序的思路和插入排序非常相似,也分已排序和未排序区间。但选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。但是不像插入排序会移动数组 选择排序会每次进行交换,如以下例子:     

4 5 6 3 2 1

第一次:    1 5 6 3 2 4

第二次:    1 2 6 3 5 4

1.时间复杂度:O(N^2)

2.空间复杂度:O(n)

3.交换次数

4.稳定性:不稳定

package com.laoyang.新手班;

/**
 * @author:Kevin
 * @create: 2023-09-26 19:08
 * @Description: 选择排序  时间: order(n^2)
 */

public class selectSort {

    public static void main(String[] args) {
        int [] arr = {5,7,23,43,1,2,45,66,32};
        selectSort(arr);
        print(arr);
    }
    public static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i] + "");
        }
    }
    public static void selectSort(int[] arr){
        if (arr == null && arr.length <2) {
            return;
        }
        int N= arr.length;
        for (int i = 0; i < N; i++) {
            // 0 - n-1
            // 1 - n-1
            // 2 - n-1
            // i - n-1
            int minIndex = i; //最小值下标
            for (int j = i+1;j<N;j++){
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr,i,minIndex);
        }
    }
    /**
     * 交换
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr,int i,int j){
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
}
   二:冒泡排序

        核心思路:冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。

        举例说明:4 5 6 3 2 1,从小到大排序。 1 2 3 4 5 6

进行排序:什么样的情况下不做任何交换了呢,那就是所有的数都在它应该在的位置;O(n)

1.时间复杂度:O(n^2)

2.空间复杂度:O(n)

3.交换次数:挺大的

4.稳定性:稳定

package Sort2;

import java.util.Arrays;

/**
 * 冒泡排序
 */

public class BubbleSort {

	public static void main(String[] args) {

		int data[] = { 4, 5, 6, 3, 2, 1 };
		int n = data.length;

		//n-1:这里是因为判断两个数是只比较一次 例如: 1  2   比较次数只会比一次
		for (int i = 0; i < n - 1; i++) {	//排序的次数
			//优化:如果所有的数都排好了,不需要交换了,就不需要冒泡了,所以直接退出
			boolean flag = false;
			// n-1-i:要减掉i是因为每次冒泡排序都会将后面的值确定,所以i就是后面已经排好的数字,所以就不需要再比较了,所以得减掉
			for (int j = 0; j < n - 1 - i; j++) {	//具体冒泡 n - 1 - i,6,5,4,3,2,1
				if (data[j] > data[j + 1]) {
					//交换
					int temp = data[j];	//用了第三个变量,不用第三个变量
					data[j] = data[j + 1];
					data[j + 1] = temp;
					flag = true;

					//异或实现
//					data[j] = data[j] ^ data[j+1];
//					data[j+1] = data[j] ^ data[j+1];
//					data[j] = data[j] ^ data[j+1];
				}
			}
			if(!flag) break;
		}
		System.out.println(Arrays.toString(data));
	}
}
/**
 * 下面是交换的时候如果不用第三方变量存储的话如何交换
 */
// a:2 b:3
// 3 2 => a:3 b:2
// 用加减
//a = a + b => a = 3+2 =5;
//b = a - b => b = 5-3 =2;
//a = a - b => a = 5-2 =3;
   2.1 如何进行简单的优化:

                1.  在交换的时候会需要第三方变量,会占空间,所以可以用异或交换。

                2. 当排好序了就不需要继续循环了,所以加flag作为标签。

       2.2 如何实现异或交换?

        异或操作可以实现交换两个数字的值的原因是因为异或操作具有以下几个性质:

  1. 任何数和0异或的结果仍然是这个数本身:a ^ 0 = a
  2. 任何数和自身异或的结果是0:a ^ a = 0
  3. 异或操作满足交换律:a ^ b = b ^ a 利用这些性质,我们可以通过异或操作实现交换两个数字的值,具体步骤如下: 假设有两个变量a和b,它们的初始值分别为a0和b0。
  4. 第一步:通过将a与b异或,将结果保存在a中:a = a ^ b。 此时,a的值为a0 ^ b0,b的值保持不变。
  5. 第二步:再将a与b异或,将结果保存在b中:b = a ^ b。 在这一步中,我们可以将上一步得到的a的值(a0 ^ b0)再与b0异或,得到的结果就是a0,即原始的a的值。 同时,由于异或操作满足交换律,所以b = (a0 ^ b0) ^ b0 = a0 ^ (b0 ^ b0) = a0 ^ 0 = a0。 此时,a的值保持不变,b的值变为a0。
  6. 第三步:最后将a与b异或,将结果保存在a中:a = a ^ b。 在这一步中,我们将上一步得到的a的值a0 ^ b0与上一步得到的b的值(a0)异或,得到的结果就是b0。
public class SwapNumbers {
    public static void main(String[] args) {
        int a = 10;
        int b = 20;
        
        System.out.println("交换前:");
        System.out.println("a = " + a);
        System.out.println("b = " + b);
        
        // 使用异或操作交换a和b的值
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        
        System.out.println("交换后:");
        System.out.println("a = " + a);
        System.out.println("b = " + b);
    }
}
        三: 快速排序

数据结构与算法-选择&冒泡&快排&计数,排序算法,算法,数据结构

45 28 80 90 50 16 100 10

基准数:一般就是取要排序序列的第一个。

第一次排序基准数:45

从后面往前找到比基准数小的数进行对换: 10 28 80 90 50 16 100 45

从前面往后面找比基准数大的进行对换: 10 28 45 90 50 16 100 80    

   10 28 16 90 50 45 100 80  

   10 28 16 45 50 90 100 80

以基准数分为3部分,左边的比之小,右边比之大:

{10 28 16} 45 {50 90 100 80}

到此第一次以45位基准数的排序完成。

1.时间复杂度:nlogn 最坏的情况就是O(n^2)

2.空间复杂度:O(n)

3.稳定性:不稳定

4.快排和归并的对比:

(1)归并排序的处理过程是由下到上的,先处理子问题,然后再合并。

(2)快排其实就是从上到下,先分区,在处理子问题,不用合并。 其优化就是优化基准数,提供一个取三个数中间的思路.

package Sort2;

public class QuiklySort {

	public static void qSort(int data[], int left, int right) {

		int base = data[left]; // 就是我们的基准数,取序列的第一个,不能用data[0]
		int ll = left; // 表示的是从左边找的位置
		int rr = right; // 表示从右边开始找的位置
		while (ll < rr) {
			// 从后面往前找比基准数小的数
			while (ll < rr && data[rr] >= base) {
				rr--;
			}
			//这里有个小技巧,如果ll < rr为true,说明 data[rr] >= base = false,就找到比基准数小的,就要交换
			if (ll < rr) { // 表示是找到有比之大的
				int temp = data[rr];
				data[rr] = data[ll];
				data[ll] = temp;
				ll++;
			}
			// 从前面往后找比基准数大的数
			while (ll < rr && data[ll] <= base) {
				ll++;
			}
			if (ll < rr) {
				int temp = data[rr];
				data[rr] = data[ll];
				data[ll] = temp;
				rr--;
			}
		}
		// 肯定是递归 分成了三部分,左右继续快排,注意要加条件不然递归就栈溢出了
		//ll:循环终止时为基准数在最中间,然后将ll左右两部分继续递归
		if (left < ll)
			qSort(data, left, ll - 1);
		if (ll < right)
			qSort(data, ll + 1, right);

	}
}
        各种排序比较:

数据结构与算法-选择&冒泡&快排&计数,排序算法,算法,数据结构

这么多种排序算法我们究竟应该怎么选择呢?

1.分析场景:稳定还是不稳定

2.数据量:数据量小的时候选什么?比如就50个数,优先选插入(5000*5000=25000000)

3.分析空间: 综上所述,没有一个固定的排序算法,都是要根据情况分析的。但是如果你不会分析的情况下 选择归并或者快排。

        四:计数排序

        如何对一个省200万学生的高考成绩(假设成绩最多只有2位小数,0~900范围)进行排序,用尽可能高效的算法。文章来源地址https://www.toymoban.com/news/detail-702895.html

package sorttest;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.UnsupportedEncodingException;
import java.io.Writer;

/**
 * 如何对一个省200万学生的高考成绩(假设成绩最多只有2位小数,0~900范围)进行排序,用尽可能高效的算法。
 *	计数排序
 */

public class CountSort {
	public static void main(String[] args) throws Exception {
		String str = null;
		String fileName = "D:\\JavaCode\\tulin\\src\\sorttest\\200w.txt";
		InputStreamReader isr = new InputStreamReader(new FileInputStream(fileName), "UTF-8");
		BufferedReader br = new BufferedReader(isr);
		int data[] = new int[2100002];
		int i = 0;
		//遍历所有的数据存到数组中
		while ((str = br.readLine()) != null) {
			double a = Double.valueOf(str);
			a = a * 100;
			data[i++] = (int) a;
			// System.out.println((int) a);
		}
		System.out.println("开始值为" + i);
		long start = System.currentTimeMillis();
		countSort(data, 0, data.length - 1);
		System.out.println("结束时间为" + (System.currentTimeMillis() - start) + "ms");
	}

	public static void countSort(int data[], int min, int max) throws Exception {
		int counts[] = new int[max + 1];
		//将所存的数字按照数组下标存储计数,
		for (int i = 0; i < data.length; i++) {
			counts[data[i]]++;
		}

		File file = new File("D:\\JavaCode\\tulin\\src\\sorttest\\200w-csort.txt");
		Writer out = new FileWriter(file);

		//同时从0开始遍历,所以也默认排好序,直接输出
		for (int i = 0; i <= max; i++) {
			if (counts[i] > 0) {
				for (int j = 0; j < counts[i]; j++) {
					out.write(((double) (i / 100.0)) + "\r\n");
				}
			}
		}
		out.close();
	}
}

到了这里,关于数据结构与算法-选择&冒泡&快排&计数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】排序算法(二)—>冒泡排序、快速排序、归并排序、计数排序

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指针版 2.4三数取中对快速排序的优化 2.5非递归版 3.归

    2024年02月08日
    浏览(54)
  • 数据结构:直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,计数排序(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 排序:使一串数据,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 插入排序的思路:把待排序数组,逐个插入到已经排好序的有序数组中,直到所有待排序数组插入完成,的到一个新的有序

    2024年02月11日
    浏览(54)
  • 【数据结构与算法】排序算法:冒泡排序,冒泡排序优化,选择排序、选择排序优化

    目录 一、冒泡排序 1、冒泡排序思想 2、冒泡排序算法的性能分析 代码实现: 二、选择排序 1、选择排序思想 2、选择排序算法的性能分析  代码实现: 1、冒泡排序思想 冒泡排序的基本思想是通过相邻元素之间的比较和交换来逐步将最大(或最小)的元素移到右边(或左边

    2024年01月19日
    浏览(50)
  • 排序 | 冒泡插入希尔选择堆快排归并计数排序

    排序算法是一种将一组数据按照特定顺序排列的算法。数据结构排序算法的选择取决于数据的特征、规模和性能需求。 接下来我们就要实现排序~~ 我们需要实现的一些功能: 冒泡排序是一种基本的排序算法,其核心思想是通过多次交换相邻元素的位置,使得每一轮循环都将

    2024年02月04日
    浏览(49)
  • 【数据结构】排序之交换排序(冒泡 | 快排)

    在之前的博客中介绍了插入排序,有需要的可以点这个链接: link,这次来介绍交换排序,包括冒泡和快排。 话不多说,正文开始。 基本思想 :所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。 交换排序的特点是:将键值较大的记录向序

    2024年02月03日
    浏览(38)
  • 排序 | 冒泡 插入 希尔 选择 堆 快排 归并 非递归 计数 基数 排序

    排序算法是一种将一组数据按照特定顺序排列的算法。数据结构排序算法的选择取决于数据的特征、规模和性能需求。 接下来我们就要实现排序~~ 我们需要实现的一些功能: 冒泡排序是一种基本的排序算法,其核心思想是通过多次交换相邻元素的位置,使得每一轮循环都将

    2024年02月04日
    浏览(54)
  • 数据结构算法--2 冒泡排序,选择排序,插入排序

    思想就是将相邻元素两两比较,当一个元素大于右侧相邻元素时,交换他们的位置,小于右侧元素时,位置不变,最终序列中的最大元素,像气泡一样,到了最右侧。 这时冒泡排序第一轮结束,数列最右侧元素9的位置可认为是一个有序区,有序区目前有一个元素. 第二轮排序

    2024年02月13日
    浏览(64)
  • 【数据结构与算法】单链表的排序算法(选择,冒泡,递归)

    目录 选择排序 冒泡排序 快速排序 合并两条链表并排序 选择排序 链表的选择排序思想与数组的排序类似,但是链表需要先找到里面最小或者最大的值,然后将这个值用改链语句进行操作 我们先看这个改链语句的操作(min是笔者打错了应该是max,但是图已经画好了就没有改)

    2024年02月04日
    浏览(56)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(85)
  • 数据结构--7.2.1排序算法(冒泡、直接选择、直接插入)

            假设含有n个记录的序列为{r1,r2,……,rn},其相应的分别为{K1,K2,……,Kn},需确定1,2,3,……,n的一种排序p1,p2,p3,……,pn;使其相应的满足kp1=kp2=kp3=kp4=……=kpn非递减(或非递增)关系,即使得序列称为一个按有序得序列{rp1,rp2,

    2024年02月07日
    浏览(73)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包