利用数组模拟的双向链表实现的插入排序

利用数组模拟的双向链表实现的插入排序

**直接插入排序思想就是将数组中的数与其前面所有数进行比较，找到小于或大于它的数插入到其相应位置**

直接上代码

	
#include

using namespace std;

const int N = 10e6 + 10;
int m, arr[N] = {6, 5, 5 , 7 ,4 ,3};

//创建双向链表
int e[N], l[N], r[N], idx, x, k;

//初始化双向链表 
void inti(){
	r[0] = 1;
	l[1] = 0;
	idx = 2;
}

//在节点为k的点右方插入 
void add(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx ++;
}

int main(){
	cin >> m;
	int t = m - 1;
	for(int i = 0; i < m; i ++ ) cin >> arr[i];
	
	inti();
	
	add(0,arr[0]);
	
	for(int i = 1; i < m; i ++ ){
		//找到第一个大于它的数
		int j = 0;
		while(j != 1){
			if(arr[i] < e[j]){
				break;
			}else{
				j = r[j];
			}
		}
		add(l[j], arr[i]);//插入到左边
	}
	
	for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << " "; 
}