投稿
  1. 首页
  2. 随笔

C&C++学习心法04数组-冒泡排序选择排序插入排序

男妓服务 • 2022-12-17 • 随笔 • 阅读 17

C&C++学习心法04数组-冒泡排序选择排序插入排序,第1张

C&C++学习心法04数组-冒泡排序/选择排序/插入排序 数组

在程序设计中，为了方便处理数据把具有相同类型的若干变量按有序形式组织起来——称为数组。

数组就是在内存中连续的相同类型的变量空间。同一个数组所有的成员都是相同的数据类型，同时所有的成员在内存中的地址是连续的

数组属于构造数据类型：

  • 一个数组可以分解为多个数组元素：这些数组元素可以是基本数据类型或构造类型
int a[10];  
struct Stu boy[10];
  • 按数组元素类型的不同，数组可分为：数值数组、字符数组、指针数组、结构数组等类别。
int a[10];
char s[10];
char *p[10];

通常情况下，数组元素下标的个数也称为维数，根据维数的不同，可将数组分为一维数组、二维数组、三维数组、四维数组等。通常情况下，我们将二维及以上的数组称为多维数组

一维数组

一维数组的定义和使用

  • 数组名字符合标识符的书写规定(数字、英文字母、下划线)
  • 数组名不能与其它变量名相同，同一作用域内是唯一的
  • 方括号[]中常量表达式表示数组元素的个数
int a[3]表示数组a有3个元素
其下标从0开始计算，因此3个元素分别为a[0],a[1],a[2]
  • 定义数组时[]内最好是常量，使用数组时[]内即可是常量，也可以是变量
#include 

int main()
{
    int a[10];//定义了一个数组，名字叫a，有10个成员，每个成员都是int类型
    //a[0]…… a[9]，没有a[10]
    //没有a这个变量，a是数组的名字，但不是变量名，它是常量
    a[0] = 0;
    //……
    a[9] = 9;

    int i = 0;
    for (i = 0; i < 10; i++)
    {
        a[i] = i; //给数组赋值
    }

    //遍历数组，并输出每个成员的值
    for (i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    printf("n");

    return 0;
}
  • 一维数组的初始化
  • 在定义数组的同时进行赋值，称为初始化。全局数组若不初始化，编译器将其初始化为零。局部数组若不初始化，内容为随机值。
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };//定义一个数组，同时初始化所有成员变量
int a[10] = { 1, 2, 3 };//初始化前三个成员，后面所有元素都设置为0
int a[10] = { 0 };//所有的成员都设置为0

 //[]中不定义元素个数，定义时必须初始化
int a[] = { 1, 2, 3, 4, 5 };//定义了一个数组，有5个成员
  • 数组名
    数组名是一个地址的常量，代表数组中首元素的地址。
#include 

int main()
{
	int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };//定义一个数组，同时初始化所有成员变量

	printf("a = %pn", a);
	printf("&a[0] = %pn", &a[0]);

	int n = sizeof(a); //数组占用内存的大小，10个int类型，10 * 4  = 40
	int n0 = sizeof(a[0]);//数组第0个元素占用内存大小，第0个元素为int，4

	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		printf("%d ", a[i]);
	}
	printf("n");

	return 0;
}


强化训练

  1. 一维数组的最值
#include 

int main()
{
	int a[] = {  1, -2, 3,- 4, 5, -6, 7, -8, -9, 10 };//定义一个数组，同时初始化所有成员变量

	int i = 0;
	int max = a[0];
	for (i = 1; i < sizeof(a) / sizeof(a[0]); i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
	}
	printf("数组中最大值为：%dn", max);

	return 0;
}
  1. 一维数组的逆置
#include 

int main()
{
	int a[] = {  1, -2, 3,- 4, 5, -6, 7, -8, -9, 10 };//定义一个数组，同时初始化所有成员变量

	int i = 0;
	int j = sizeof(a) / sizeof(a[0]) -1;
	int tmp;

	while (i < j)
	{
		tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
		i++;
		j--;
	}

	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		printf("%d ", a[i]);
	}
	printf("n");

	return 0;
}
冒泡排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字
的位置”这一 *** 作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的
顶端，所以这个算法才被称为“冒泡排序”。

    1. 比较相邻元素， 如果第一个比第二个大， 就交换他们两个
    1. 对每一对相邻的元素做同样的工作， 执行完毕后， 找到第一个最大值
    1. 重复以上步骤， 每次比较 次数 - 1， 直到不需要比较









在冒泡排序中，第 1 轮需要比较 n -1 次，第 2 轮需要比较 n -2 次……第 n -1 轮需
要比较 1 次。因此，总的比较次数为 (n -1) +(n -2) +…+1 ≈ n^2
/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。
不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输
入数据正好以从小到大的顺序排列，那么便不需要任何交换 *** 作；反过来，输入数据要
是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时
间复杂度为 O(n^2)。
一层循环/右侧开始版

#include 
using namespace std;
int main(){
    int arr[] = {5, 9, 3, 1, 2, 8, 4, 7, 6};
    int len = sizeof(arr)/sizeof(arr[0]);
    for (int j = len-1; j > 0; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "t";
    }
    cout<< endl;
    cout<< "================================" << endl;

    for (int j = len-1; j > 1; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "t";
    }
    cout<< endl;
    cout<< "================================" << endl;


    for (int j = len-1; j > 2; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "t";
    }
    cout<< endl;
    cout<< "================================" << endl;

    for (int j = len-1; j > 3; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "t";
    }
    cout<< endl;
    cout<< "================================" << endl;

    for (int j = len-1; j > 4; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "t";
    }
    cout<< endl;
    cout<< "================================" << endl;

    for (int j = len-1; j > 5; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "t";
    }
    cout<< endl;
    cout<< "================================" << endl;
    for (int j = len-1; j > 7; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "t";
    }
    cout<< endl;
    cout<< "================================" << endl;
}




#include 
using namespace std;
int main(){
    int arr[] = {5, 9, 3, 1, 2, 8, 4, 7, 6};
    int count = 0;
    int len = sizeof(arr)/sizeof(arr[0]);
    for (int i = 0; i < len -1; ++i) {
        for (int j = len-1; j > i; --j) {
            count++;
            if (arr[j-1] > arr[j]){
                int temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "t";
    }
    cout<< endl;
    cout<<  count << endl;
}
左侧开始版 
#include 
using namespace std;

int main(){
    int arr[] = { 4,2,8,0,5,7,9, 1,3 };
    int len = sizeof(arr)/sizeof(arr[0]);
    // len-1-i 每次最右面的值是最大的,不用比较
    for (int i = 0; i < len-1; ++i) {
        for (int j = 0; j < len-1-i; ++j) {
            if (arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }

    for (int i = 0; i < len; ++i) {
        cout << arr[i]<< "t";
    }
}
选择排序（Selection-Sort）

先把最小的拿出来
剩下的， 再把最小的拿出来
剩下的， 再把最小的拿出来
。。。
每次选择还没处理的元素里最小的元素

选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一 *** 作的算法。在序列中寻找最小值时使用的是线性查找。

比如: 对数字1~9进行排序。 使用线性查找在数据中寻找最小值，于是我们找到了最小值 1



  • 一层版
#include 
using namespace std;
int main(){
    int arr[] = {6, 1, 7, 8, 9, 3, 5, 4, 2};
    int  len = sizeof(arr)/sizeof(arr[0]);
    int minIndex = 0;
    for (int j = 0; j < len; ++j) {
        if (arr[j] < arr[minIndex])
            minIndex = j;
    }
    cout<<"minIndex = "<< minIndex <
 

最终版
 

#include 
using namespace std;

int main(){
    int arr[] = { 6, 1, 7, 8, 9, 3, 5, 4, 2};
    int len = sizeof(arr)/sizeof(arr[0]);

    for (int i = 0; i < len - 1; ++i) {
        int minIndex = i;
        for (int j = i; j < len; ++j) {
            if(arr[j] < arr[minIndex])
                minIndex = j;
        }
        // 小优化
        if (minIndex != i){
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    for (int i = 0; i < len; ++i) {
        cout << arr[i] <<"t";

    }
    cout < 

 
插入排序 


 每次处理一张牌， 把这张牌插入到前面已经排好序的牌中
 插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插人排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插人到已排序区域内合适的位置上。
 
 
 
 
 
 
 
 

#include 
using namespace std;
// 冒泡排序
void insertionSort(int arr[], int len);
void printArray(int array[], int len);

int main (){
    int arr[] = {5, 9, 3, 1, 2, 8, 4, 7, 6};
    cout<< "insertionSort排序前" < 0; j--) {
//            if (arr[j] < arr[j-1]){
//                int temp = arr[j];
//                arr[j] = arr[j-1];
//                arr[j-1] = temp;
//            } else{
//                break; //此时就是合适的插入位置
//            }
//        }
//    }

    // 写法2
    for (int i = 1; i < len; i++) {
        // 将 i 位置的值 插入到合适的位置
        for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
            int temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }
    }
}

void printArray(int array[], int len){
    cout<<"[";
    for (int i = 0; i < len; i++) {
        if (i == len-1)
            cout<< array[i] <<"]"<二维数组
 5.3.1 二维数组的定义和使用
 二维数组定义的一般形式是：
 类型说明符 数组名[常量表达式1][常量表达式2]
 其中常量表达式1表示第一维下标的长度，常量表达式2 表示第二维下标的长度。
 

int a[3][4];
  命名规则同一维数组
 

 定义了一个三行四列的数组，数组名为a其元素类型为整型，该数组的元素个数为3×4个，即：
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5698807.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
男妓服务 男妓服务 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存