【数据结构初阶】直接插入排序和希尔排序&链表排序

void InsertSort(int* a, int n)
{
	//n个数据,第一个默认有序,因此只需进行n-1趟插入排序
	for (int i = 0; i < n - 1; i++)
	{
		//定义end为已有序序列的数元素的下标的最大值为i
		int end = i;
		//定义待排序的元素的下标中的最小值对应的元素为temp
		int temp = a[i + 1];
		//每一趟进行插入排序
		while (end >= 0)
		{
			//如果已有序序列的元素a[end]比待排序的元素temp大,则将a[end]后移一位
			if (a[end] > temp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else//否则就退出循环
			{
				break;
			}
		}
		//跳出while循环有两种情况:
		//1.end<0,也就是说已有序序列的所有元素都比完了,也就是待排序的那个元素比已有序序列的所有元素都小
		//2.待排序的元素temp比已有序序列的某元素a[end]大,提前跳出循环

		//将temp放在下标为end+1的位置
		a[end + 1] = temp;
	}
}

//直接插入排序,假设排升序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int temp = a[i + 1];
		while (end >= 0)
		{
			if (a[end] > temp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}

		a[end + 1] = temp;
	}
}

void PrintArr(int* a, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d\t", a[i]);
	}
}

int main()
{
	int a[] = { 12,4,46,23,541,32 };
	int sz = sizeof(a) / sizeof(a[0]);
	InsertSort(a, sz);

	PrintArr(a, sz);
	return 0;
}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap  >  1 )
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
		printf("gap==%d:", gap);
		PrintArr(a, n);
	}
}


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

	return 0;
}

//C 语言中的clock()函数的头文件是time.h
int main()
{
	srand((unsigned int)0);
	int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; i++)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	printf("InsertSort：%d\n", end1-begin1);

	int begin2 = clock();
	InsertSort(a2, N);
	int end2 = clock();
	printf("ShellSort：%d\n", end2-begin2);
	
	free(a1);
	free(a2);
	a1 = a2 = NULL;
	return 0;
}

struct ListNode* insertionSortList(struct ListNode* head){
    //第一步:建立新链表，从原链表中取出结点，记为cur
    struct ListNode* Guard=(struct ListNode*)malloc(sizeof(struct ListNode));
    Guard->next=head;
    struct ListNode* cur=head->next;
    head->next=NULL;
    
    //第二步:从前往后遍历新链表，比较newcur->val和cur->val的大小，选择合适的位置插入
    while(cur)
    {
        struct ListNode* next=cur->next;
        struct ListNode* newprev=Guard;
        struct ListNode* newcur=Guard->next;
        while(newcur)
        {
            if(cur->val>newcur->val)
            {
                newprev=newcur;
                newcur=prev->next;
            }
            else     
            {
                break;
            }
        }
        prev->next=cur;
        cur->next=newcur;

        cur=next;
    }
    struct ListNode* newhead=Guard->next;
    free(Guard);
    Guard=NULL;
    
    return newhead;
}