数据结构与算法（一）

                                注：以下代码均基于C++

---

快排算法

思路: 取数组q[]的中间值为参考, 将数组的首尾两端与数组的中间值比较(首端比中间值小, 尾端比中间值大)直至首尾两端均不符合条件.此时再将不符合条件的两个值交换.

void quickSort(int q[], int l, int r)
{
	if(l >= r) return;	//递归算法的终止条件
  
	int x = q[l + r >> 1], i = l - 1, j = r + 1;  //取x作为比较的中间值
  
	while(i < j)
	{
    	do i++;
    	while(q[i] < x);
    
    	do j--;
    	while(q[j] > x);
    
    	// 如果还满足i < j且q[i] < q[j],交换q[i]与q[j]
    	if(i < j)
    	{
      		int t = q[i];
      		q[i] = q[j];
      		q[j] = t;
    	}
  	}
    
  	quickSort(q, l, j), quickSort(q, j + 1, r);  //递归算法
}

归并排序算法

思路: 将数组q[]从中间分成长度相等的两段, 设其长度中间值为mid. 依次比较q[1]与q[mid + 1]等的大小, 不断将两者其中更小者放入临时数组temp[]中, 直至两段中的一段全部被放入. 此时再将未放完的一段数组全部放入临时数组temp[]中.

void mergeSort(int q[], int l, int r)
{
	if(l >= r) return;  //归并算法终止条件
	
	int mid = l + r >> 1, i = l, j = mid + 1, t = 0;  //定义数组中间位数等
	int temp[100010];  //定义临时数组用来保存部分数据
	
	mergeSort(q, l, mid), mergeSort(q, mid + 1, r);  //归并算法
	
	while(i <= mid && j <= r)  //
	{
		if(q[i] <= q[j]) temp[t++] = q[i++];
		else temp[t++] = q[j++];
	}
	while(i <= mid) temp[t++] = q[i++];
	while(j <= r) temp[t++] = q[j++];
    
    for(i = l, t = 0;i <= r;i++, t++) q[i] = temp[t];  //将临时数组中的元素放回到数组q[]中 
}

---

更新中…