脚本宝典收集整理的这篇文章主要介绍了[算法]“简简单单”的插入排序,你还没掌握吗?,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
大家好,我是melo,一名大二上软件工程在读生,经历了一年的摸滚,现在已经在工作室里边准备开发后台项目啦。 不过这篇文章呢,还是想跟大家聊一聊数据结构与算法,学校也是大二上才开设了数据结构这门课,希望可以一边学习数据结构一边积累后台项目开发经验。 前几篇,我们都是聊了聊数据结构,也该来聊点新花样了,接触一些更考验思维和逻辑的算法,现在这一阶段的算法了,我们主要先来谈论的都是排序算法,这节就从最“简单"的插入排序开始吧!
插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。
总结就是: 把前n-1个看成有序了,然后把第n个插入到前边中的适当位置即可,成为新的有序表
更具体详细的思路过程都嵌入在代码的注释里了喔!
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* sortArray(int* nums, int numsSize, int* returnSize){
//从第二个数开始遍历
for(int i=1;i<numsSize;i++){
//保存待插入的值
int insertValue=nums[i];
int insertIndex=0;
for(int j=i-1;j>=0;j--){
//若待插入的值小于索引值,证明要索引值需要后移,空出这个位置给插入值
if(insertValue<nums[j]){
nums[j+1]=nums[j];
//记录待插入的位置
insertIndex=j;
}
}
//跳出循环后,把这个数插入到指定位置
nums[insertIndex]=insertValue;
}
/*returnSize = (int*)malloc(numsSize*sizeof(int));
for(int i=0;i<numsSize;i++){
returnSize[i]=nums[i];
}*/
*returnSize=numsSize;
return nums;
}
实际上因为前n-1个数已经有序了,所以如果我们待插入值还大于最后一个数时,则无须继续遍历下去了
原数组是升序的,每轮循环中只需要比较1次便进行下一轮的循环,一共需要比较O(n)次。
原数组是降序的,数组中任意两个数都要比较一次,共比较O(n^2)次。
只用了一个哨兵位置
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* sortArray(int* nums, int numsSize, int* returnSize){
int insertValue = 0;
int j;
//从第二个数开始遍历
for(int i=1;i<numsSize;i++){
//保存待插入的值
insertValue=nums[i];
//因为本身有序,若待插入的数还大于最后一个数,则无须继续遍历下去了
for(j=i-1;j>=0 && insertValue<nums[j];j--){
//若待插入的值小于索引值,证明要索引值需要后移,空出j这个位置给插入值
nums[j+1]=nums[j];
}
//跳出循环后,把这个数插入到指定位置
nums[j+1]=insertValue;
}
/*returnSize = (int*)malloc(numsSize*sizeof(int));
for(int i=0;i<numsSize;i++){
returnSize[i]=nums[i];
}*/
*returnSize=numsSize;
return nums;
}
★
设置哨兵在0的话,可以省去j>0这一判断,因为走到哨兵就自然会停下来了
”
#include "allinclude.h" //DO NOT edIT this line
void InsertSort(RcdSQList &L)
{ // Add your code here
for(int i=2;i<=L.length;i++){
int j=i-1;
//记录哨兵
L.rcd[0].key=L.rcd[i].key;
//找到要插入的位置(往哨兵的方向,哨兵在前边)
while(L.rcd[j].key>L.rcd[L.length+1].key){
L.rcd[j+1].key=L.rcd[j].key;
j--;
}
//出循环时,j+1即是要插入的位置
L.rcd[j+1].key=L.rcd[L.length+1].key;
}
}
因为我们要体现哨兵的作用,得体现出走到哨兵自然就停下来了的作用 原本我们上边是i从0到末尾,然后用一个j去从i前边一个元素遍历到哨兵的位置 现在我们哨兵放在后边了,我们得反过来思考。 让i从后往前遍历,这样j才能从前往后,遍历到哨兵的位置
//刚好跟上边相反,i是从后往前去遍历
for(int i=L.length-1;i>=0;i--){
int j=i+1;
//若本身就小于后边一个了,则无须进行任何移动
if(L.rcd[i].key>L.rcd[j].key){
//记录哨兵
L.rcd[L.length+1].key=L.rcd[i].key;
//找到要插入的位置(j是往后去走,因为哨兵在后边)
while(L.rcd[j].key<L.rcd[L.length+1].key){
L.rcd[j-1].key=L.rcd[j].key;
j++;
}
//出循环时,j-1即是要插入的位置
L.rcd[j-1].key=L.rcd[L.length+1].key;
}
}
for(从第二个开始遍历)
a[j+1]=insertVal
其实数组跟链表的区别在于,数组可以方便的找到前一个,而链表不能,所以我们需要额外用一个PRe指针来记录上一个,同时可以进行优化
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* insertionSortList(struct ListNode* head){
struct ListNode* drumyHead=(struct ListNode*)malloc(sizeof(struct ListNode));
drumyHead->next=head;
//待插入元素p(直接从第二个元素开始)
struct ListNode* p=drumyHead->next->next;
while(p){
struct ListNode* q=drumyHead;
struct ListNode* pos=NULL;
//若还未遍历到待插入元素的上一个位置
while(q->next!=p){
//若遍历到的当前元素的下一位大于待插入元素,则应将待插入元素插到当前元素的下一位
if(q->next->val > p->val){
//记录待插入位置
pos=q;
//得跳出阿!因为跟之前从后往前找不一样,这里是从前往后找,比如原本是 2 3 4 1
//发现2>1,此时就已经是正确位置了,得跳出
break;
}
//移动q
q=q->next;
}
//再让q移动到p的前一个位置,方便操作
while(q->next!=p){
q=q->next;
}
//出循环时,q已经到待插入元素p的前一位
if(pos!=NULL){
//注意顺序
//先让q的next=p的next
q->next=p->next;
p->next=pos->next;
pos->next=p;
}
//移动p
p=p->next;
}
return drumyHead->next;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* insertionSortList(struct ListNode* head){
struct ListNode* drumyHead=(struct ListNode*)malloc(sizeof(struct ListNode));
drumyHead->next=head;
//待插入元素p(直接从第二个元素开始)
struct ListNode* p=drumyHead->next->next;
//记录待插入元素的前驱,记得初始化为第一个元素!!!
struct ListNode* pre=drumyHead->next;
while(p){
//先跟前驱比较
if(p->val>pre->val){
pre=p;
p=p->next;
continue;
}
struct ListNode* q=drumyHead;
struct ListNode* pos=NULL;
//若还未遍历到待插入元素的上一个位置
while(q->next!=p){
//若遍历到的当前元素的下一位大于待插入元素,则应将待插入元素插到当前元素的下一位
if(q->next->val > p->val){
//记录待插入位置
pos=q;
//得跳出阿!因为跟之前从后往前找不一样,这里是从前往后找,比如原本是 2 3 4 1
//发现2>1,此时就已经是正确位置了,得跳出
break;
}
//移动q
q=q->next;
}
//让q移动到p的前一个位置(因为前边break了),方便操作
while(q->next!=p){
q=q->next;
}
//出循环时,q已经到待插入元素p的前一位
if(pos!=NULL){
//注意顺序
//先让q的next=p的next
q->next=p->next;
p->next=pos->next;
pos->next=p;
}
//更新前驱
pre=p;
//移动p
p=p->next;
}
return drumyHead->next;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* insertionSortList(struct ListNode* head){
struct ListNode* drumyHead=(struct ListNode*)malloc(sizeof(struct ListNode));
drumyHead->next=head;
//待插入元素p(直接从第二个元素开始)
struct ListNode* p=drumyHead->next->next;
//记录待插入元素的前驱,记得初始化为第一个元素!!!
struct ListNode* pre=drumyHead->next;
struct ListNode* q;
struct ListNode* pos;
while(p){
// //先跟前驱比较(这样效率低了好多,这样要300ms,换成下边while判断只需要40ms)
// if(p->val>pre->val){
// pre=p;
// p=p->next;
// continue;
// }
q=drumyHead;
pos=NULL;
//先判断是否小于前驱,不是的话直接不用进循环了!!!
//若还未遍历到待插入元素的上一个位置
while(q->next!=p&&p->val<pre->val){
//若遍历到的当前元素的下一位大于待插入元素,则应将待插入元素插到当前元素的下一位
if(q->next->val > p->val){
//记录待插入位置
pos=q;
//得跳出阿!因为跟之前从后往前找不一样,这里是从前往后找,比如原本是 2 3 4 1
//发现2>1,此时就已经是正确位置了,得跳出
break;
}
//移动q
q=q->next;
}
//没必要了,因为有pre可以记录p的上一个位置了
// //让q移动到p的前一个位置(因为前边break了),方便操作
// while(q->next!=p){
// q=q->next;
// }
//出循环时,判断pos,得知是否需要插入
if(pos!=NULL){
//注意顺序
//先让q的next=p的next
pre->next=p->next;
p->next=pos->next;
pos->next=p;
}
//更新前驱
pre=p;
//移动p
p=p->next;
}
return drumyHead->next;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* insertionSortList(struct ListNode* head){
struct ListNode* drumyHead=(struct ListNode*)malloc(sizeof(struct ListNode));
drumyHead->next=head;
//待插入元素p(直接从第二个元素开始)
struct ListNode* p=drumyHead->next->next;
//记录待插入元素的前驱,记得初始化为第一个元素!!!
struct ListNode* pre=drumyHead->next;
struct ListNode* q;
struct ListNode* pos;
while(p){
// //先跟前驱比较
// if(p->val>pre->val){
// pre=p;
// p=p->next;
// continue;
// }
//直接在这里进行比较,尽量不要continue
if(p->val<pre->val){
q=drumyHead;
pos=NULL;
//若还未遍历到待插入元素的上一个位置
while(q->next!=p){
//若遍历到的当前元素的下一位大于待插入元素,则应将待插入元素插到当前元素的下一位
if(q->next->val > p->val){
//记录待插入位置
pos=q;
//得跳出阿!因为跟之前从后往前找不一样,这里是从前往后找,比如原本是 2 3 4 1
//发现2>1,此时就已经是正确位置了,得跳出
break;
}
//移动q
q=q->next;
}
// //让q移动到p的前一个位置(因为前边break了),方便操作
// while(q->next!=p){
// q=q->next;
// }
//出循环时,q已经到待插入元素p的前一位
if(pos!=NULL){
//注意顺序
//先让q的next=p的next
pre->next=p->next;
p->next=pos->next;
pos->next=p;
}
}
//更新前驱
pre=p;
//移动p
p=p->next;
}
return drumyHead->next;
}
调用下边的stamp方法,分别在插入排序前打印时间和插入排序后打印时间
#include <ctime>
#include <string>
#include <chrono>
#include <sstream>
#include <iomanip>
#include <iostream>
// use strftime to format time_t into a "date time"
std::string date_time(std::time_t posix)
{
char buf[20]; // Big enough for 2015-07-08 10:06:51
std::tm tp = *std::localtime(&posix);
return {buf, std::strftime(buf, sizeof(buf), "%F %T", &tp)};
}
std::string stamp()
{
using namespace std;
using namespace std::chrono;
// get absolute wall time
auto now = System_clock::now();
// find the number of milliseconds
auto ms = duration_cast<milliseconds>(now.time_since_epoch()) % 1000;
// build output string
std::ostringstream oss;
oss.fill('0');
// convert absolute time to time_t seconds
// and convert to "date time"
oss << date_time(system_clock::to_time_t(now));
oss << '.' << setw(3) << ms.count();
return oss.str();
}
int main()
{
std::cout << stamp() << 'n';
}
耗时接近39秒
耗时3ms???? 差距着实有点大,有点小迷
LeetCode上有时给我们的都是不带头结点的链表,我们可以自己构造一个虚拟头结点!
以上是脚本宝典为你收集整理的[算法]“简简单单”的插入排序,你还没掌握吗?全部内容,希望文章能够帮你解决[算法]“简简单单”的插入排序,你还没掌握吗?所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。