金华做网站报价,百度广告怎么推广,主机做网站服务器怎么设置,适合做外链的网站冒泡排序
起泡排序#xff0c;别名“冒泡排序”#xff0c;该算法的核心思想是将无序表中的所有记录#xff0c;通过两两比较关键字#xff0c;得出升序序列或者降序序列。
算法步骤
比较相邻的元素。如果第一个元素大于第二个元素#xff0c;就交换它们。对每一对相邻…冒泡排序
起泡排序别名“冒泡排序”该算法的核心思想是将无序表中的所有记录通过两两比较关键字得出升序序列或者降序序列。
算法步骤
比较相邻的元素。如果第一个元素大于第二个元素就交换它们。对每一对相邻的元素作相同的操作从开始第一对到末尾的最后一对。针对所有的元素重复以上操作每次出来最后一个
算法理解
例如对无序表{4938659776132749}进行升序排序的具体实现过程如图 1 所示 图 1 第一次起泡
如图 1 所示是对无序表的第一次起泡排序最终将无序表中的最大值 97 找到并存储在表的最后一个位置。具体实现过程为
首先 49 和 38 比较由于 3849所以两者交换位置即从1到2的转变然后继续下标为 1 的同下标为 2 的进行比较由于 4965所以不移动位置3中 65 同 97 比较得知两者也不需要移动位置直至497 同 76 进行比较7697两者交换位置如5所示同样 97135、97276、97497所以经过一次冒泡排序最终在无序表中找到一个最大值 97第一次冒泡结束
由于 97 已经判断为最大值所以第二次冒泡排序时就需要找出除 97 之外的无序表中的最大值比较过程和第一次完全相同。 经过第二次冒泡最终找到了除 97 之外的又一个最大值 76比较过程完全一样这里不再描述。 通过一趟趟的比较一个个的“最大值”被找到并移动到相应位置直到检测到表中数据已经有序或者比较次数等同于表中含有记录的个数排序结束这就是起泡排序。 代码实现
#include iostream
using namespace std;void swap(int *a, int *b){//交换a和b的位置int temp;temp *a;*a *b;*b temp;
}
int main()
{int array[8] {49,38,65,97,76,13,27,49};//有多少记录就需要多少次冒泡当比较过程所有记录都按照升序排列时排序结束for (int i 0; i 8; i){int key0;//每次开始冒泡前初始化 key 值为 0//每次起泡从下标为 0 开始到 8-i 结束for (int j 0; j18-i; j){if (array[j] array[j1]){key1;swap(array[j], array[j1]);}}//如果 key 值为 0表明表中记录排序完成if (key0) {break;}}for (i 0; i 8; i){cout array[i] ;}return 0;
}运行结果
13 27 38 49 49 65 76 97总结
使用起泡排序算法其时间复杂度同实际表中数据的无序程度有关。若表中记录本身为正序存放则整个排序过程只需进行 n-1n 为表中记录的个数次比较且不需要移动记录若表中记录为逆序存放最坏的情况则需要 n-1趟排序进行 n(n-1)/2 次比较和数据的移动。所以该算法的时间复杂度为O(n2)。
快速排序
快速排序本质上是可以说是冒泡排序基础上的递归分治法它也是分治算法在排序算法上的一种经典应用。
算法思想
快速排序是通过多次比较和交换来实现有序的。在一次排序中把将要排序的元素分成两个独立的子数组其中一个子数组的所有元素全大于另一个组数组的所有元素然后继续递归排序这两部分。
算法思想步骤
从序列中挑出一个元素称之为边界或者基准重新排序数列所有元素比基准值小的放在基准前面所有元素比基准值大的放在基准后面相同的数可以放在任意一边。这个操作结束后该基准就处于序列的中间位置这个操作称之为分区操作递归吧小于基准元素的组数组和大于基准元素的子数组排序
算法理解 代码实现
#include iostream
using namespace std;#define MAX 9
//单个记录的结构体
typedef struct {int key;
}SqNote;
//记录表的结构体
typedef struct {SqNote r[MAX];int length;
}SqList;
//此方法中存储记录的数组中下标为 0 的位置时空着的不放任何记录记录从下标为 1 处开始依次存放
int Partition(SqList *L,int low,int high){L-r[0]L-r[low];int pivotkeyL-r[low].key;//直到两指针相遇程序结束while (lowhigh) {//high指针左移直至遇到比pivotkey值小的记录指针停止移动while (lowhigh L-r[high].keypivotkey) {high--;}//直接将high指向的小于支点的记录移动到low指针的位置。L-r[low]L-r[high];//low 指针右移直至遇到比pivotkey值大的记录指针停止移动while (lowhigh L-r[low].keypivotkey) {low;}//直接将low指向的大于支点的记录移动到high指针的位置L-r[high]L-r[low];}//将支点添加到准确的位置L-r[low]L-r[0];return low;
}
void QSort(SqList *L,int low,int high){if (lowhigh) {//找到支点的位置int pivotlocPartition(L, low, high);//对支点左侧的子表进行排序QSort(L, low, pivotloc-1);//对支点右侧的子表进行排序QSort(L, pivotloc1, high);}
}
void QuickSort(SqList *L){QSort(L, 1,L-length);
}
int main() {SqList *L new SqList;L-length8;L-r[1].key49;L-r[2].key38;L-r[3].key65;L-r[4].key97;L-r[5].key76;L-r[6].key13;L-r[7].key27;L-r[8].key49;QuickSort(L);for (int i1; iL-length; i) {cout L-r[i].key ;}return 0;
}运行结果
13 27 38 49 49 65 76 97总结
快速排序算法的时间复杂度为O(nlogn)是所有时间复杂度相同的排序方法中性能最好的排序算法。
